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

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

2、,Ti时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=。 编程任务 设计一个动态规划算法，对1jL，计算出所有的C( n,j )。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性 数据输入由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n1时，若jTn,即第n种钱币面值比所兑换零钱数小,因此有。当k为时，C(n,j)达到最小值，有P(T(k0),j)=P(T()，j-T()+1若j=Tn，即用n种钱币兑换零钱，第n种钱币面值与兑换零钱数j相等，此时有C(n,j)=C(n,Tn)=1；若jTn，

3、即第n种钱币面值比所兑换零钱数大，因此兑换零钱只需考虑前n-1种钱币即可，故有C(n,j)=C(n-1,j)，且P(T(n-1),j)=0。从以上讨论可知该问题具有重叠子问题性质。（2） 根据分析建立正确的递归关系。答： （3） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。答：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为；算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为：五、问题解决（1） 根据对问题的分析，写出解决办法。答：设数组T中存放的是n种钱币递增的不同面值，所要找的钱数为M,M由用户输入；数组Cj表示利用数Tn兑换零钱数为j时所用

4、的最少钱币个数，即最优值；Pij(1=i=n)表示按照上述最优值兑换零钱J时用到钱币面值为第i种钱币的个数。（2） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。for (i=0;ikind;i+)for (j=i+1;jTj)Swap(Ti,Tj);long temptotal=total;if (total0)for (i=kind-1;i=0;i-)Swap(Ti,Tkind-1);if (Tkind-10)ckind-1=temptotal/Tkind-1;long tempcount=0;while(

5、ckind-10)&(ckind-1=0;j-)if (temptotal0)&(Tj0)cj=temptotal/Tj;temptotal=temptotal-Tj*cj;tempcount=tempcount+cj;if (tempcount0)&(tempcountmincount)&(temptotal=0)mincount=tempcount;ckind-1=ckind-1-1;temptotal=total;tempcount=0;时间复杂度：从上面算法可知，最优值c的计算过程中，最外层为循环for(j=1;j1&flag=0)循环，而while(k1&flag=0)循环中又嵌套着

6、三个并列的for循环。因此本算法最坏情况下的复杂度是O(M*)；最好的情况当然是里面for循环的条件不满足而不执行，此时的复杂度为O(M*n)。其中：M表示需要兑换的零钱数，对于M来说，该值一般不是很大，对于钱币来说，M会小于100元，即10 000分；n表示钱币的种类，n值一般不会很大如钱币总的有13种(从1分，2分，100元)。经过以上分析，如是最坏情况时的复杂度应为O(M*),则该值对于内存和运行速度较小的自动售货机等的应用前景则不会很好。但本算法中的递归结构在MTn时，有。可见对于钱币j=M时，求c(n,j)时，并不要求对从1ij，的所有情况都要求c(n,i)+1，而是只求。其中：1k

7、n。钱币一般只有13种左右，因此其效率大为上升。最坏的情况下需要执行，而M小于100元即10000分，远大于n。本算法的动态规划算法的时间复杂性比该问题的一般动态规划算法的效率要好得多。该算法的时间复杂性是数量级的对于应用于自动售货机等运行速度较慢的机器来说是不成问题的。空间复杂度：从上面算法可知，用到了三个数组，分别为Tn，cj，Pij。其中：i=n,j=M。空间复杂性主要由P1j决定，为O(Mn)。P(i,j)中的i指的Tn中的值对于钱币来说一般n为13左右。该算法的空间复杂度为O(M x n)=O(f)，而M小于100元即10 000分，远大于n。该算法动态规划的空间复杂性比该问题的一般

8、动态规划的效率要好得多。该算法的空间复杂性为数量级，这对于应用到小内存的自动售货机来说是没有任何问题的。（3） 你在调试过程中发现了怎样的问题？又做了怎样的改进？答：在调试过程中，我发现对于该算法最主要的在于矩阵Ci,j的求解，而算法的递归关系没有弄明白，所以在求解Ci,j时总是出现问题，后来在查询了资料后，将Ci,j递归关系的实现改为cj=temptotal/Tj;temptotal=temptotal-Tj*cj;tempcount=tempcount+cj;解决了该问题。（4） 写出用你的测试数据按照算法的流程填写的算法中的存储结构。C1,2,3=0,2,9。六、实验结果总结 1.程序运

9、行截图：2.回答以下问题：（1） 算法实现的复杂度在问题规模很大时可以接受吗？答：可以接受，因为动态规划算法有很好的效率，所以当问题复杂度很大时，就不会影响到算法的运行时间。（2） 如果不用动态规划方法还能想到其他的解决方式吗？和动态规划相比会有更好的效率吗？答：对于找硬币问题，有时候贪心算法也能解决，但不如动态规划求解有效率，所以采用动态规划方法是一个很好的选择。（3） 所选用的数据结构合适吗？答：采用了数组的数据结构，合适，因为该数据结构能够支持对于数组中的元素的随机访问，而且方便查询。（4） 该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些情况吗，测试结果如何？（5） 叙述通过实验你对动态规划方法的理解及其优缺点答：优点：动态规划方法有效利用了子问题的重叠性，减少了大量的计算。而且动态规划的使用也非常简单，只需要问题满足最优子结构、子问题重叠