作业帮 > 综合 > 作业

为找零问题设计一个动态规划算法:给定金额n以及各种面额d1,d2,d3,……dm的硬币(个数不限),求总金额

来源:学生作业帮 编辑:神马作文网作业帮 分类:综合作业 时间:2024/11/13 10:09:12
为找零问题设计一个动态规划算法:给定金额n以及各种面额d1,d2,d3,……dm的硬币(个数不限),求总金额
题我昨天都已经做完了,不过还是谢谢你们了。
为找零问题设计一个动态规划算法:给定金额n以及各种面额d1,d2,d3,……dm的硬币(个数不限),求总金额
f[j]表示金额为j的最少数.
f[j+di]:=Min{ f[j+di],f[j] }
f数组初始化为无穷大,f[0]初始为0,枚举i从1到m,枚举j从0到n-di
最后的答案是f[n]