Python程序:找出用给定硬币表示 n 元的方案数

Python程序:找出用给定硬币表示 n 元的方案数

假设我们有面额为 (1, 2, 5 和 10) 的硬币。我们要找出用这些面值的硬币组成 n 元的方法有多少种。我们有一个名为 count 的数组,它有 4 个元素,其中 count[0] 指示 1 元硬币的数量,count[1] 指示 2 元硬币的数量,依此类推。

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

  • 102 + 51 + 2*1 = 27

  • 102 + 23 + 1*1 = 27

  • 101 + 53 + 2*1 = 27

  • 101 + 51 + 42 + 41 = 27

等等……

要解决这个问题,我们将按照以下步骤进行 −

  • denom := [1,2,5,10]
  • A := 一个大小为 (n+1) 的数组,并将其填充为 0
  • B := 从 A 新建一个列表
  • 对于 i 在 0 到 count[0] 和 n 中的最小值的范围内,执行以下操作:
    • A[i] := 1
  • 对于 i 在 1 到 3 的范围内,执行以下操作:
    • 对于 j 在 0 到count[i] 的范围内,执行以下操作:
      • 对于 k 在 n+1-j*denom[i] 的范围内,执行以下操作:
      • B[k+jdenom[i]] := B[k+jdenom[i]] + A[k]
    • 对于 j 在 0 到 n 的范围内,执行以下操作:
      • A[j] := B[j]
      • B[j] := 0
  • 返回 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))

输入

27, [8,4,3,2]

输出

<

18

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程