文档介绍：动态规划解找零钱问题实验报告一、实验目的(1)熟练掌握动态规划思想及教材中相关经典算法。(2)掌握用动态规划解题的基本步骤,能够用动态规划解决一些问题。二、实验内容与实验步骤(1)仔细阅读备选实验的题目,选择一个(可选多个)作为此次实验题目,设计的程序要满足正确性,代码中有关键的注释,书写格式清晰,简洁易懂,效率较高,利用C++的模板,设计的程序通用性好,适合各种合理输入,并能对不合理输入做出正确的提示。(2)可供选择的题目有以下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程序运行结束时,。、实验环境四、问题分析(1)分析要解决的问题,给出你的思路,可以借助图表等辅助表达。答:这个问题用动态规划来解,归结到动态规划上面就变成了无限背包问题(因为收银台的硬币默认是无穷的,但一种改进版本可以考察有限硬币的情况)。区别在于,现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的,即每次选择都可以选择任何一种硬币。首先,找零钱问题具有最优子结构性质:兑换零钱问题的最优子结构表述:对于任意需要找的钱数j,一个利用T[n]中的n个不同面值钱币进行兑换零钱的最佳方案为P(T(1),j),P(T(2),j),...,P(T(n),j),即此时的最少钱币个数C(n,j)=åP(T(k),j)k=1n,则P(T(2),j),...,P(T(n),j)一定是利用T[n]中n个不同的面值钱币对钱数j=j-P(T(1),j)*T(1)进行兑换零钱的最佳方案。其次,找零钱问题具有重叠于问题性质:a)当n=1时,即只能用一种钱币兑换零钱,钱币的面值为T[0],有j%T[1]¹0¥C(1,j)=j/T[1]j%T[1]=0b)当n1时,若jT[n],即第n种钱币面值比所兑换零钱数小,因此有C(n,j)=min{C(n,j-T[k])+1}1£k£n。当k为k0(1£i£n)时,C(n,j)达到最小{值,有P(T(k0),j)=P(T(k0),j-T(k0))+1若j=T[n],即用n种钱币兑换零钱,第n种钱币面值与兑换零钱数j相等,此时有C(n,j)=C(n,T[n])=1;P(i,j)=P(i,T[n])={1,i=T[n]0,i¹T[n]若j从以上讨论可知该问题具有重叠子问题性质。(2)根据分析建立正确的递归关系。答:j%T[1]¹0¥C(1,j)=j/T[1]j%T[1]=0{C(i,j)={C(i-1,j)0£j<T[i];min(C(i-1,j),C(i,j-T[i])+1)j³T[i](3)分析利用你的想法解决该问题可能会有怎样的时空复杂度。答:算法的时间复杂度主要取决于程序的两个循环,所以算法的时间复杂度2O(n);算法执行过程中引入了一个二维数组,随着输入规模的增大,所为2O(n)需要的空间复杂度为:五、问题解决(1)根据对问题的分析,写出解决办法。答:设数组T[]中存放的是n种钱币递增的不同面值,所要找的钱数为M,M由用户输入;数组C[j]表示利用数T[n]兑换零钱数为j时所用的最少钱币个数,即最优值;P[i][j](1(2)描述你在进行实现时,主要的函数或操作内部的主要算法;分析这个算法的时、空复杂度,并说明你设计的巧妙之处,如有创新,将其清晰的表述。for(i=0;iT[j]){Swap(T[i],T[j]);}}longtemptotal=total;if(total0)for(i=kind-1;i=0;i--){Swap(T[i],T[kind-1]);if(T[kind-1]0){c[kind-1]=temptotal/T[kind-1];longtempcount=0;while((c[kind-1]0)&&(c[kind-1]}temptotal=temptotal-T[kind-1]*c[kind-1];for(j=kind-2;j=0;j--)if((temptotal0)&&(T[j]0)){c[j]=temptotal/T[j];temptotal=temptotal-T[j]