Python 程序寻找用给定硬币获得 n 卢比的方法

pythonserver side programmingprogramming更新于 2025/12/23 15:40:17

假设我们给出了面额为 (1、2、5 和 10) 的硬币。我们必须找出有多少种方法可以用这些面额排列 n。我们有一个名为 count 的数组，它有 4 个元素，其中 count[0] 表示硬币数量为 1，count[1] 表示硬币数量为 2，以此类推。

因此，如果输入为 n = 27 count = [8,4,3,2]，则输出将为 18，因此有 18 种可能的组合，其中一些是

10*2 + 5*1 + 2*1 = 27
10*2 + 2*3 + 1*1 = 27
10*1 + 5*3 + 2*1 = 27
10*1 + 5*1 + 4*2 + 4*1 = 27

等等...

为了解决这个问题，我们将遵循以下步骤 −

denom := [1,2,5,10]
A := 一个大小为 (n + 1) 的数组并用 0 填充
B := 来自 A 的新列表
对于范围为 0 到 (count[0] 和 n 的最小值) 的 i，执行
- A[i] := 1
对于范围为 1 到 3 的 i，执行
- 对于范围为 0 到 count[i] 的 j，执行
  - 对于范围为 0 到 n + 1 - j *denom[i] 的 k，执行
    - B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]
- 对于 0 到 n 范围内的 j，执行
  - A[j] := B[j]
  - B[j] := 0
return A[n]

示例

让我们看看下面的实现以便更好地理解

denom = [1,2,5,10]

def solve(n, count):
   A = [0 for _ in range(n+1)]
   B = list(A)
   for i in range(min(count[0], n) + 1):
      A[i] = 1
   for i in range(1, 4):
      for j in range(0, count[i] + 1):
         for k in range(n + 1 - j *denom[i]):
            B[k + j * denom[i]] += A[k]
      for j in range(0, n + 1):
         A[j] = B[j]
         B[j] = 0
   return A[n]

n = 27
count = [8,4,3,2]
print(solve(n, count))