数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学使用给定硬币获得n卢比的方法的Python程序
假设我们有面值为(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 + 1 - j *denom[i]的k，执行：
- 对于范围从0到n的j，执行：
- A[j] := B[j]
- B[j] := 0
- 对于范围从0到count[i]的j，执行：
- 返回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
更新于：2021年10月12日
373 次查看
广告