Python程序:查找使用印度货币面值获得n卢比的方案数


假设我们有有限数量的以下面值的硬币(1卢比,2卢比,5卢比和10卢比)。我们需要找到用这些硬币凑成n卢比总额的方案数。我们有一个大小为4的数组count,其中count[0]表示1卢比硬币的数量,count[1]表示2卢比硬币的数量,以此类推。

所以,如果输入像n = 25,count = [7,3,2,2],那么输出将是9。

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

  • 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从0到n + 1 - j *denom[i],执行以下操作:
        • B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]
    • 对于j从0到n,执行以下操作:
      • A[j] := B[j]
      • B[j] := 0
  • 返回A[n]

示例

让我们看看下面的实现以获得更好的理解:

Open Compiler
denom = [1,2,5,10] def solve(n, count): A = [0] * (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 = 25 count = [7,3,2,2] print(solve(n, count))

输入

25, [7,3,2,2]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

9

更新于: 2021年10月23日

156 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告