动态规划解找零钱问题实验报告

《动态规划解找零钱问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、、实验目的(1)熟练掌握动态规划思想及教材屮相关经典算法。(2)掌握用动态规划解题的基本步骤，能够用动态规划解决一些问题。:、实验内容与实验步骤(1)仔细阅读备选实验的题目，选择一个(可选多个)作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂,效率较高，利用C++的模板，设计的程序通用性好，适合各种合理输入,并能对不合理输入做出正确的提示。(2)可供选择的题目有以下2个：(1)找零钱问题(难度系数为3)★问题描述设有n种不同面值的硬币，各硬币的面值存于数组T[l:n]中。现要用这些面值的硬币来找钱

2、，可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时，可找岀钱数j的最少硬币个数记为C(i,j)o若只用这些硬币面值，找不出钱数j时，记C(i,j)=-0★编程任务设计一个动态规划算法，对lWjWL,计算出所有的C(n,j)o算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性★数据输入由文件input.txt提供输入数据。文件的第1行中有I个正整数n5v=13),表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j。★结果输岀程序运行结束时，将计算出的所需

3、最少硬币个数输出到文件output.txt中O输入文件示例input.txt31259输出文件示例output.txt3三、实验环境操作系统Windows7调试软件VC++6.0上机地点综合楼211四、问题分析(1)分析要解决的问题，给出你的思路，可以借助图表等辅助表达。答：这个问题用动态规划来解，归结到动态规划上面就变成了无限背包问题(因为收银台的硬币默认是无穷的，但一种改进版本可以考察有限硬币的情况)。区别在于，现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的，即每次选择都可以选择任何一种硬币。首先，找零钱问

4、题具有最优子结构性质：兑换零钱问题的最优子结构表述：对于任意需要找的钱数j,一个利用T[n]中的n个不同面值钱币进行兑换零钱的最佳方案为P(T(l),j),P(T(2),j),...,P(T(n),j),即此时的最少钱币个数C(")=£P(T(k)，J),则P(T(2),j),・・・,P(T(n),j)—定是利用T[n]屮n个不同的面值钱币对钱数j=j・P(T(l),j)*T(l)进行兑换零钱的最佳方案。其次，找零钱问题具有重叠于问题性质：a)当n=l时，即只能用一种钱币兑换零钱，钱币的面值为T[0],有C(hJ)二OOJ/T[]

5、b)当n>l时，C(/7,y)=min{C(H，7-TR])+l}T[n],B

6、J第n种钱币面值比所兑换零钱数小,因此有o当k为ko(15i£n)时,c(n,j)达到最小值，有P(T(kO),j)=P(T(k。),j・T(ko))+l若j=T[n],即用n种钱币兑换零钱，第n种钱币面值与兑换零钱数j相等，此时有C(n,j)=C(n,T[n])=l；"7)=P(z,血)=饴爲若j

7、)=Oo从以上讨论可知该问题具有重叠子问题性质。(1)根据分析建立正确的递归关系。答:C(l,J)=h⑴/%T[1]^O;%ni]=oC(i,j)二鶯C爲如T仙)(1)分析利用你的想法解决该问题可能会有怎样的时空复杂度。答：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为。⑴2)；算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为：°(朋)五、问题解决(1)根据对问题的分析，写出解决办法。答：设数组T[]中存放的是n种钱币递增的不同面值，所要找的钱数为M,M由用户输入；数组C[j]表示利用数T

8、[n]兑换零钱数为j时所用的最少钱币个数，即最优值；P[i][j](lv二iv二n)表示按照上述最优值兑换零钱J吋用到钱币面值为第i种钱币的个数。(2)描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。for(i=0;iTU]){Swap(T[i],T[j]);longtemptotal=total;if(total>0)for(i=kind-l;i>=O;i-){Swap(

9、T[i],T[kind-l]);if(T[kind-l]>0){c[kind-1]=temptotal/T[kind-1];longtempcount=();whilc((c[kind-1]>0)&&(c[kind-1]<=minco