程序查找可使用Python中的硬币和数量制作的不同硬币总和的数量？

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个称为硬币的值列表，另一个名为相同长度的数量的列表。第i个硬币的值是硬币[i]，我们目前有第i个硬币的数量[i]。我们必须找到通过使用这些硬币的非空组可以获得的不同硬币总和值的数量。

因此，如果输入像硬币= [1、2、5]数量= [1、2、1]，那么输出将是10，因为我们可以得到以下不同的硬币总和[1] = 1，[2] ] = 2，[1,2] = 3，[2,2] = 4，[5] = 5，[1,5] = 6，[2,5] = 7，[1,2,5] = 8，[2,2,5] = 9，[1,2,2,5] = 10

为了解决这个问题，我们将按照以下步骤操作：

定义一个功能rec()。这需要我，res

if i is same as size of coins , then
   return
for k in range 0 to quantities[i] + 1, do
   cur := res + k * coins[i]
   insert cur into fres
   rec(i + 1, cur)
From the main method, do the following:
fres := a new set
rec(0, 0)
return size of fres - 1

示例

class Solution:
   def solve(self, coins, quantities):
      def rec(i, res):
         if i == len(coins):
            return
         for k in range(0, quantities[i] + 1):
            cur = res + k * coins[i]
            fres.add(cur)
            rec(i + 1, cur)
      fres = set()      rec(0, 0)
      return len(fres) - 1
ob = Solution()coins = [1, 2, 5]
quantities = [1, 2, 1]
print(ob.solve(coins, quantities))

输入值

[1, 2, 5], [1, 2, 1]

输出结果

10

以上是 程序查找可使用Python中的硬币和数量制作的不同硬币总和的数量？ 的全部内容， 来源链接： utcz.com/z/321569.html