Python 硬币兑换问题
作者:GorillaNotes 时间:2022-04-03 06:30:09
硬币兑换问题:
给定总金额为A的一张纸币,现要兑换成面额分别为a1,a2,....,an的硬币,且希望所得到的硬币个数最少。
# 动态规划思想 dp方程式如下
# dp[0] = 0
# dp[i] = min{dp[i - coins[j]] + 1}, 且 其中 i >= coins[j], 0 <= j < coins.length
# 回溯法,输出可找的硬币方案
# path[i] 表示经过本次兑换后所剩下的面值,即 i - path[i] 可得到本次兑换的硬币值。
def changeCoins(coins, n):
if n < 0: return None
dp, path = [0] * (n+1), [0] * (n+1) # 初始化
for i in range(1, n+1):
minNum = i # 初始化当前硬币最优值
for c in coins: # 扫描一遍硬币列表,选择一个最优值
if i >= c and minNum > dp[i-c]+1:
minNum, path[i] = dp[i-c]+1, i - c
dp[i] = minNum # 更新当前硬币最优值
print('最少硬币数:', dp[-1])
print('可找的硬币', end=': ')
while path[n] != 0:
print(n-path[n], end=' ')
n = path[n]
print(n, end=' ')
if __name__ == '__main__':
coins, n = [1, 4, 5], 22 # 输入可换的硬币种类,总金额n
changeCoins(coins, n)
来源:https://blog.csdn.net/XX_123_1_RJ/article/details/80353497
标签:Python,硬币兑换
0
投稿
猜你喜欢
asp如何设置cookie的过期时间
2008-02-29 13:36:00
如何在mac环境中用python处理protobuf
2021-02-26 08:42:06
ASP编程菜鸟易犯的一个错误
2008-10-29 13:27:00
JavaScript缓动库
2009-05-25 12:50:00
5个很好的Python面试题问题答案及分析
2023-05-12 18:45:23
Python数据分析之 Matplotlib 3D图详情
2021-03-05 21:20:33
使用简单工厂模式来进行Python的设计模式编程
2021-02-17 11:53:50
python数据可视化的那些操作你了解吗
2023-11-04 15:18:55
Keras使用ImageNet上预训练的模型方式
2021-03-01 10:08:51
Python程序暂停的正常处理方法
2023-07-17 23:21:47
巧妙的Sql函数日期处理方法
2009-05-25 17:59:00
Python远程linux执行命令实现
2023-11-17 14:48:14
PHP引用(&)各种使用方法实例详解
2023-11-01 18:12:43
python 使用装饰器并记录log的示例代码
2022-02-17 02:15:03
python按行读取文件,去掉每行的换行符\\n的实例
2022-06-01 03:49:43
详解使用Pytorch Geometric实现GraphSAGE模型
2021-09-30 21:30:18
python list转置和前后反转的例子
2022-04-26 10:39:55
python获取对象信息的实例详解
2022-04-30 14:55:50
python机器学习之神经网络实现
2022-01-10 08:10:05
戴着锁链跳舞
2009-08-20 13:06:00