算法设计与分析P3-4

《算法设计与分析P3-4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、问题描述设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。（1）当只用硬币面值T[1],T[2],…,T[i]时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=∞。给出C(i,j)的递归表达式及其初始条件。其中，1≤i≤n,1≤j≤L.(2)设计一个动态规划算法，对于1≤j≤L，计算出所有的C(n,j).算法只允许使用一个长度为L的数组。用L和n作为变量表示算法的时间复杂性。（3）在C(n,j),1<=j<=L，已计算出的情况下，设计一个贪心算法，对任意钱

2、数m<=L，给出用最少硬币找钱m的方法。当C（n,m）≠∞时，算法的计算时间为O(n+C(n,m))。分析这个问题用动态规划来解，归结到动态规划上面就变成了无限背包问题。区别在于，现在我们需要求一个最少的硬币数而不是最大值。但是选择的情况也是相同的，即每次选择都可以选择任何一种硬币。首先，找零钱问题具有最优子结构性质：兑换零钱问题的最优子结构表述：对于任意需要找的钱数j，一个利用T[n]中的n个不同面值钱币进行兑换零钱的最佳方案为P(T(1),j)，P(T(2),j),...,P(T(n),j)，即此时的最少钱币个数C(n,j)=k=0nP(T(k),j)则P(T(2),j)

3、,...,P(T(n),j)一定是利用T[n]中n个不同的面值钱币对钱数j=j-P(T(1),j)*T(1)进行兑换零钱的最佳方案。其次，找零钱问题具有重叠于问题性质：a)当n=1时，即只能用一种钱币兑换零钱，钱币的面值为T[0]，有（2） 根据分析建立正确的递归关系：复杂度：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为：O(n2)；算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为：O(n2)算法：#include#includeusingnamespacestd;#defineMAX2000

4、2#defineINF9999999#definemin(a,b)(a)>(b)?(b):(a)intT[11],Coins[11],n;//硬币面值数组T[],可以使用的各种面值的硬币个数数组Coins[],n种不同面值的硬币intc[MAX];//数组c[]存放要找的最少硬币个数intm;//要找的钱数mvoidinit(){inti;cout<<"输入硬币的面值种数：";cin>>n;cout<<"输入硬币面值及其此面值硬币的个数："<>T[i]>>Coins[i];}cout<<"输入要找的钱数：";cin

5、>>m;}intmain(intargc,char*argv[]){init();for(inti=0;i<=m;++i)c[i]=INF;c[0]=0;for(inti=0;i=T[i];--k)c[k]=min(c[k],c[k-T[i]]+1);}}if(c[m]!=INF)cout<<"最少硬币个数为："<

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

7、用前景则不会很好。但本算法中的递归结构在L>T[n]时，有可见对于钱币j=L时，求c(n,j)时，并不要求对从1≤i≤j，的所有情况都要求c(n,i)+1，而是只求。其中：1≤k≤n。钱币一般只有13种左右，因此其效率大为上升。最坏的情况下需要执行而M小于100元即10000分，远大于n。本算法的动态规划算法的时间复杂性比该问题的一般动态规划算法的效率要好得多。该算法的时间复杂性是103数量级的．对于应用于自动售货机等运行速度较慢的机器来说是不成问题的。贪心算法由贪心算法可知尽量用大面值的硬币组合来找钱