资源描述：
《钱币组合问题课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、COIN:钱币组合问题报告人:卢芳学号:080320045时间:2008.11.1问题描述:设有n种不同的钱币各若干张，可用这n种钱币产生许多不同的面值。试设计一个算法，计算给定的某个面值，能有多少种不同的产生方法。例如:有1分3张，2分3张，5分1张，则能组成7分面值的方法有：3个1分+2个2分，1个1分+3个2分，2个1分+1个5分，1个2分+1个5分共四种。编程任务：对于给定的n种不同钱币，编程计算某个给定面值能有多少种不同的产生方法。数据输入：由文件input.txt提供输入数据。文件的第1行有1个正整数n(1<=n<=10)，表
2、示有n中不同的钱币。第2行有n个数，分别表示每种钱币的面值。第3行有n个数，分别表示每种钱币的张数k(0<=k<=10)。第4行有1个数，表示给定的面值m(1<=m<=20001)。结果输出：将计算出的给定面值的不同产生方法种数输出到文件output.txt。输入文件示例输出文件示例input.txtoutput.txt341253317算法设计:这题我最先想到的算法是:深搜+剪枝主要的递归式是:f(m,i)+=f(m-a[i]*j,t)(当i>=1)其中,i,t为搜索的层次,a[i]:第i种钱币面值,j∈(1..k[i]),t∈(i-1
3、,0);故思想是:以上的搜索递归式再加上适当的剪枝.例如:input.txt3n=3125a[0]=1,a[1]=2,a[2]=5331k[0]=3,k[1]=3,k[2]=17m=7搜索过程如下:f(7,0)f(7,1)f(7,2)++f(1,0)f(3,0)f(5,0)f(0,0)f(2,0)f(2,1)=0=====11101代码实现:intsum=0;//Globalvariableintf(intm,inti,inta[],intb[],inta_sum[])//第i种钱币之前（包括第i种）的m值钱币的表示种类{//a[]=mo
4、n_value[],b[]=k_value[]if(0==i){if(m>a[i]*b[i])returnsum;elseif((m%a[i]==0)&&(m/a[i]<=b[i]))returnsum++;}elseif(i>=1){intt;if(m>a_sum[i])//剪枝returnsum;elseif(m==a_sum[i])returnsum++;else{for(intj=1;j<=b[i];j++){t=i;if(m>a[i]*j){while(t>0){//深搜f(m-a[i]*j,t-1,a,b,a_sum);t--
5、;}}elseif(m==a[i]*j){sum++;j=b[i]+1;}elsej=b[i]+1;//退出for循环}returnsum;}}}PS:动态规划思想(DP):G[i,j]:表示面值为i的在第j种钱币出现时的表示种数G[i,j]+=G[i–a[j]*kk,j-1]其中,a[j]表示第j种钱币面值,kk∈[1..k[j]],该式子满足最优子结构性质,并且要求m的最优值为G[m,n],m为要求表示的面值,n为钱币种数.算法实现时,G可以用两个一维数组交替表示.例如:input.txt3n=3125a[0]=1,a[1]=2,a[
6、2]=5331k[0]=3,k[1]=3,k[2]=17m=7i=1,g[0,1]=1,g[1,1]=1,g[2,1]=1,g[3,1]=1,g[4,1]=0,g[5,1]=0,g[6,1]=0,g[7,1]=0;i=2,g[0,2]=1,g[1,2]=1,g[2,2]=g[2,1]+g[0,1]=2,g[3,2]=g[3,1]+g[1,1]=2,g[4,2]=g[4,1]+g[2,1]+g[0,1]=2,g[5,2]=g[5,1]+g[3,1]+g[1,1]=2,g[6,2]=g[6,1]+g[4,1]+g[2,1]+g[0,1]=3,
7、g[7,2]=g[7,1]+g[5,1]+g[3,1]+g[1,1]=2i=3,g[0,3]=1,g[1,3]=1,g[2,2]=2,g[3,3]=2,g[4,3]=2,g[5,3]=g[5,2]+g[0,2]=3,g[6,3]=g[6,2]+g[1,2]=3,g[7,3]=g[7,2]+g[2,2]=4(最终结果)算法效率分析比较:用动态规划(dp)思想:时间复杂度为:○(m)用深搜的思想:最坏情况下:○(n)但是实际上由于剪枝,使深搜时间大大减少,本题,两个算法相比较,如果深搜没有剪枝的话,明显比dp算法要更多的时间;而本题用dp会比
8、深搜效率高,但是其计算过程中也存在求解了一些没有用到的子问题.
