文档介绍：一、实验目的
熟练掌握动态规划思想及教材中相关经典算法。
掌握用动态规划解题的基本步骤,能够用动态规划解决一些问题。
二、实验内容与实验步骤
仔细阅读备选实验的题目,选择一个(可选多个)作为此次实验题目,设计的程序要满足正确性,代码中有关键的注释,书写格式清晰,简洁易懂,效率较高,利用C++的模板,设计的程序通用性好,适合各种合理输入,并能对不合理输入做出正确的提示。
可供选择的题目有以下2个:
(i)找零钱问题(难度系数为3)
« 问题描述
设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱,可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时,可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值,找不出钱数j时,记C(i,j)=∞。
« 编程任务
设计一个动态规划算法,对1≤j≤L,计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性
« 数据输入
。文件的第1行中有1个正整数n(n<=13),表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。
« 结果输出
程序运行结束时,。
输入文件示例
输出文件示例

3
1 2 5
9
3
三、实验环境
操作系统
Windows 7
调试软件
VC++
上机地点
综合楼211
四、问题分析
分析要解决的问题,给出你的思路,可以借助图表等辅助表达。
答:这个问题用动态规划来解,归结到动态规划上面就变成了无限背包问题(因为收银台的硬币默认是无穷的,但一种改进版本可以考察有限硬币的情况)。区别在于,现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的,即每次选择都可以选择任何一种硬币。
首先,找零钱问题具有最优子结构性质:
兑换零钱问题的最优子结构表述:对于任意需要找的钱数j,一个利用T[n]中的n个不同面值钱币进行兑换零钱的最佳方案为P(T(1),j),P(T(2),j),...,P(T(n),j),即此时的最少钱币个数,则P(T(2),j),...,P(T(n),j)一定是利用T[n]中n个不同的面值钱币对钱数j=j-P(T(1),j)* T(1)进行兑换零钱的最佳方案。
其次,找零钱问题具有重叠于问题性质:
当n=1时,即只能用一种钱币兑换零钱,钱币的面值为T[0],有
b)当n>1时,
若j>T[n],即第n种钱币面值比所兑换零钱数小,因此有。当k为时,C(n,j)达到最小值,有P(T(k0),j)=P(T(),j-T())+1
若j=T[n],即用n种钱币兑换零钱,第n种钱币面值与兑换零钱数j相等,此时有C(n,j)=C(n,T[n])=1;
若j<T[n],即第n种钱币面值比所兑换零钱数大,因此兑换零钱只需考虑前n-1种钱币即可,故有C(n,j)=C(n-1,j),且P(T(n-1),j)=0。
从以上讨论可知该问题具有重叠子问题性质。
根据分析建立正确的递归关系。
答:

分析利用你的想