算法设计与分析P3-4

问题描述设有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，已计算出的情况下，设计一个贪心算法，对任意钱数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)∑则P(T(2),j),...,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)算法：#includeiostream#includecstringusingnamespacestd;#defineMAX20002#defineINF9999999#definemin(a,b)(a)(b)?(b):(a)intT[11],Coins[11],n;//硬币面值数组T[],可以使用的各种面值的硬币个数数组Coins[],n种不同面值的硬币intc[MAX];//数组c[]存放要找的最少硬币个数intm;//要找的钱数mvoidinit(){inti;cout输入硬币的面值种数：;cinn;cout\n输入硬币面值及其此面值硬币的个数：endl;for(i=0;in;++i){cinT[i]Coins[i];}cout\n输入要找的钱数：;cinm;}intmain(intargc,char*argv[]){init();for(inti=0;i=m;++i)c[i]=INF;c[0]=0;for(inti=0;in;++i){for(intj=1;j=Coins[i];++j){for(intk=m;k=T[i];--k)c[k]=min(c[k],c[k-T[i]]+1);}}if(c[m]!=INF)cout\n最少硬币个数为：c[m]endl;elsecout-1endl;return0;}运行结果：时间复杂度：从上面算法可知，最优值c[j]的计算过程中，最外层为循环for(j=1;j=L;j++)嵌套着while(k1&&flag==0)循环，而while(k1&flag==0)循环中又嵌套着三个并列的for循环。因此本算法最坏情况下的复杂度是O(L*2n)；最好的情况当然是里面for循环的条件不满足而不执行，此时的复杂度为O(L*n)。其中：L表示需要兑换的零钱数，对于L来说，该值一般不是很大，对于钱币来说，L会小于100元，即10000分；n表示钱币的种类，n值一般不会很大．如钱币总的有13种(从1分，2分，⋯，100元)。经过以上分析，如是最坏情况时的复杂度应为O(L*2n),则该值对于内存和运行速度较小的自动售货机等的应用前景则不会很好。但本算法中的递归结构在LT[n]时，有可见对于钱币j=L时，求c(n,j)时，并不要求对从1≤i≤j，的所有情况都要求c(n,i)+1，而是只求。其中：1≤k≤n。钱币一般只有13种左右，因此其效率大为上升。最坏的情况下需要执行而M小于100元即10000分，远大于n。本算法的动态规划算法的时间复杂性比该问题的一般动态规划算法的效率要好得多。该算法的时间复杂性是103数量级的．对于应用于自动售货机等运行速度较慢的机器来说是不成问题的。贪心算法由贪心算法可知尽量用大面值的硬币组合来找钱，可以使使用的硬币最少。而贪心算法对最少硬币问题的解决总是可以得到最优解很好的近似解。例如：9分面值的硬币5枚，8分面值的硬币5枚，2分面值的硬币8枚，要找25分钱。设要找的钱为m，硬币种类为n，t[i](0i=n)为硬币的面值，c[i]为可以使用的各种面值的硬币个数,k[i]为第i种面值的硬币可以使用的最多个数（k[i]=min{m/t[i],c[i]}）(1)将硬币依面值大小排序982(2)按面值种类划分不同情况有多少种面值就划分多少种情况.每种情况的第一枚硬币面值各不一样,其后对剩余的硬币按面值从大到小排列.划分为三个情况：982，892，298。对应k[i]为：k[0]=3,k[1]=3,k[2]=8得到近似最优解群为9分1枚,8分2枚;9分1枚,8分1枚,2分4枚;9分1枚,2分8枚.算法优化1,在寻找最优组合过程中，有些情况可以不予考虑。比如上例中2982,在以小面值的硬币为第一个的情况中，在寻找最优组合时，会遇到两种情况：a、使用硬币个数要比以大面值的硬币(如9和8)为第一个的情况大得多。b、寻找到的组合与前面的情况有重复。完整程序代码如下：#includestdio.h#includefstream.h#includestdlib.hintn,money;structctype{intvalue;intcoin;};templateclasstypevoidmake2Darray(type**&x,introws,intcols){x=newtype*[rows];for(inti=0;irows;i++)x[i]=newtype[cols];}voidswap(ctype&a,ctype&b){ctypetemp;temp=a;a=b;b=temp;}intpartition(ctypearray[],intp,intr){inti,j;ctypekey;i=p;j=r+1;key=array[p];while(true){while(array[++i].valuekey.value);while(array[--j].valuekey.value);if(i=j)break;swap(array[i],array[j]);}array[p]=array[j];array[j]=key;returnj;}voidquicksort(ctypearray[],intp,intr){intq;if(pr){q=partition(array,p,r);quicksort(array,p,q-1);quicksort(array,q+1,r);}}voidmain(){ifstreaminput(input.txt);ofstreamoutput(output.txt);inputn;int*coins=newint[n+1];ctype*T=newctype[n+1];for(inti=1;i=n;i++){inputT[i].value;inputT[i].coin;}inputmoney;quicksort(T,1,n);/*for(i=1;i=n;i++){coins[i]=T[i].coin;}*/intmax=0;for(i=1;i=n;i++)max+=T[i].coin;max+=10;int*min=newint[money+1];min[0]=0;int**cnum;make2Darray(cnum,money+1,n+1);for(i=0;i=money;i++)for(intj=1;j=n;j++)cnum[i][j]=0;if(T[1].value==1){min[1]=1;cnum[1][1]=1;}elsemin[1]=max;intj=2;while(j=money){min[j]=max;i=1;while((i=n)&&(j=T[i].value)){intcoinumber=cnum[j-T[i].value][i];coinumber++;if((min[j]1+min[j-T[i].value])&&(coinumber=T[i].coin)){for(intk=1;k=n;k++)cnum[j][k]=cnum[j-T[i].value][k];cnum[j][i]++;min[j]=1+min[j-T[i].value];}i++;}j++;}if(min[money]!=max)outputmin[money];elseoutput-1;}