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

一、实验目的

（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作为变量来表示算法的计算时间复杂性  数据输入

由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n

程序运行结束时，将计算出的所需最少硬币个数输出到文件

output.txt中。

输入文件示例 input.txt

3 1 2 5

输出文件示例 output.txt 3

9

三、实验环境

四、问题分析

（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]0

b)当n>1时，

若j>T[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） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。

答：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度

2

O(n)；算法执行过程中引入了一个二维数组，随着输入规模的增大，所为

2

O(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]); } }

long temptotal=total; if (total>0) 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]; long tempcount=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 ((temptotal>0)&&(T[j]>0)) { c[j]=temptotal/T[j]; temptotal=temptotal-T[j]*c[j]; tempcount=tempcount+c[j]; }

if ((tempcount>0)&&(tempcount

时间复杂度：

从上面算法可知，最优值c[』]的计算过程中，最外层为循环for(j=1;j1&&flag==0)循环，而

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

C(n,j)minC(n,jT[k])1

1kn

。可见对于钱币j=M时，求c(n,j)时，并不要

求对从1≤i≤j，的所有情况都要求c(n,i)+1，而是只求C(n,jT[k])1。其中：1≤k≤n。钱币一般只有13种左右，因此其效率大为上升。最坏

23

O(Mn)O(n)，而M小于100元即10000分，远的情况下需要执行

大于n。本算法的动态规划算法的时间复杂性比该问题的一般动态规划算法的效率要好得多。该算法的时间复杂性是10数量级的．对于应用于自动售货机等运行速度较慢的机器来说是不成问题的。

空间复杂度：从上面算法可知，用到了三个数组，分别为T[n]，c[j]，P[i][j]。其中：i

3

该算法动态规划的空间复杂性比该问题的一般动态规划的效率要好得

210多。该算法的空间复杂性为数量级，这对于应用到小内存的自动售货

机来说是没有任何问题的。

（3） 你在调试过程中发现了怎样的问题？又做了怎样的改进？

答：在调试过程中，我发现对于该算法最主要的在于矩阵C[i,j]的求解，而算法的递归关系没有弄明白，所以在求解C[i,j]时总是出现问题，后来在查询了资料后，将C[i,j]递归关系的实现改为

c[j]=temptotal/T[j];temptotal=temptotal-T[j]*c[j];tempcount=tempcount+c[j];解决了该问题。

（4） 写出用你的测试数据按照算法的流程填写的算法中的存储结构。 C[1,2,3]={0,2,9}。

六、实验结果总结

1.程序运行截图：

2.回答以下问题：

（1） 算法实现的复杂度在问题规模很大时可以接受吗？

答：可以接受，因为动态规划算法有很好的效率，所以当问题复杂度很大时，就不会影响到算法的运行时间。

（2） 如果不用动态规划方法还能想到其他的解决方式吗？和动态规划相

比会有更好的效率吗？

答：对于找硬币问题，有时候贪心算法也能解决，但不如动态规划求解有效率，所以采用动态规划方法是一个很好的选择。 （3） 所选用的数据结构合适吗？

答：采用了数组的数据结构，合适，因为该数据结构能够支持对于数组中的元素的随机访问，而且方便查询。 （4） 该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到

的这些情况吗，测试结果如何？

（5） 叙述通过实验你对动态规划方法的理解及其优缺点

答：优点：动态规划方法有效利用了子问题的重叠性，减少了大量的计算。而且动态规划的使用也非常简单，只需要问题满足最优子结构、子问题重叠性、无后效性即可。通常可以利用分置思想构造出子问题的分解方法，就可以利用动态规划。

缺点：动态规划的缺点并不是最快的方法，只是解决某一类型的问题的工具或者优化某些 NPC问题的时间效率。动态规划的很重要的一点就是用大量空间换取时间上的优化，所以这并不是一个完美的方法。

七、附录

参考资料：《算法导论》