;。 ,C++、最少硬币问题,问题描述详见pdf文件。:日期:,我们当只有一种面值的硬币时,可以用钱M减去相应的面值,剩下的钱数再减去相应的面值,以此类推,每减去一次面额的钱数,相应的增加一个硬币,直至硬币数不够或者剩余钱数小于相应面额为止,由此我们可以得到一个递归方程,设d[m+1]存储相应的最少硬币个数,即d(m)=d(m-k)+1;k为相应的面值;其次,由于硬币个数或面值有限,我们把钱M分成2部分,一部分是可以兑换相应的硬币,一部分是没有充足的现金来兑换,所以我们把d(0)初始化为0,意味0元的钱能兑换0个硬币,而把d数组其余的位置置为99999,如果钱能兑换,则最后d(m)的值会由d(0)加上“1”相应循环次数,,反之则会得到99999,;lasschangecoin{ publicstaticvoidchange_cion(intm,int[]T,int[]Coin){ int[]c=newint[m+1]; c[0]=0; for(inti=1;i<=-1;i++)c[i]=99999; for(intr=1;r<=-1;r++){//硬币的面值 for(intj=Coin[r];j>0;j--){//硬币的个数 for(intk=m;k>=T[r];k--){ c[k]=(c[k],c[k-T[r]]+1); } } } if(c[m]>=99999) ("钱找不开"); else (c[m]); } publicstaticvoidmain(String[]args){ Scannerscan=newScanner(); System
实验三-2动态规划 来自淘豆网m.daumloan.com转载请标明出处.
