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

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

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

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

3、xt312593三、实验环境操作系统Windows7调试软件VC++6.0上机地点综合楼211四、问题分析（1）分析要解决的问题，给出你的思路，可以借助图表等辅助表达。答：这个问题用动态规划来解，归结到动态规划上面就变成了无限背包问题（因为收银台的硬币默认是无穷的，但一种改进版本可以考察有限硬币的情况）。区别在于，现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的，即每次选择都可以选择任何一种硬币。首先，找零钱问题具有最优子结构性质：兑换零钱问题的最优子结构表述：对于任意需要找的钱数j，一个利用T[n]中的n个不同面值钱币进行兑换零钱的最佳方案为P(T(1),j)，P

4、(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)进行兑换零钱的最佳方案。其次，找零钱问题具有重叠于问题性质：a)当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])

5、=1；若j

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

7、T[kind-1]>0){c[kind-1]=temptotal/T[kind-1];longtempcount=0;while((c[kind-1]>0)&&(c[kind-1]<=mincount)){tempcount=c[kind-1];temptotal=temptotal-T[kind-1]*c[kind-1];for(j=kind-2;j>=0;j--)if((temptotal>0)&&(T[j]>0)){c[j]=tempto