实验三-2动态规划

算法设计与分析实验报告学号姓名班级上课地点教师上课时间实验四动态规划1.实验目的1.1．理解动态规划算法的主要设计思想；1.2．掌握用动态规划算法策略解决最小合并问题和资源分配问题。2.实验环境2.1Eclipse,C++2.2Window103.实验内容1、最少硬币问题，问题描述详见pdf文件。4.教师批改意见签字：日期：成绩实验报告细表1实验题目1.1算法设计思想首先要找到实现算法的递归方程，我们当只有一种面值的硬币时，可以用钱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”相应循环次数，皆由Math.min方法可以得出最小兑换硬币值，反之则会得到99999，以此判断为兑换失败1.2程序源码importjava.util.Scanner;publicclasschangecoin{publicstaticvoidchange_cion(intm,int[]T,int[]Coin){int[]c=newint[m+1];c[0]=0;for(inti=1;i=c.length-1;i++)c[i]=99999;for(intr=1;r=T.length-1;r++){//硬币的面值for(intj=Coin[r];j0;j--){//硬币的个数for(intk=m;k=T[r];k--){c[k]=Math.min(c[k],c[k-T[r]]+1);}}}if(c[m]=99999)System.out.println(钱找不开);elseSystem.out.println(c[m]);}publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);System.out.println(请输入钱数m);intm=scan.nextInt();System.out.println(请输入硬币种类数);intcount=scan.nextInt();int[]T=newint[count+1];int[]Coin=newint[count+1];System.out.println(请输入硬币的面值和硬币的个数);for(inti=1;i=count;i++){T[i]=scan.nextInt();Coin[i]=scan.nextInt();}change_cion(m,T,Coin);}}1.3实验结论（结果验证）1.4心得体会刚开始，找到方程的递归式还是挺简单，但是由于硬币的个数受限，还有不懂如何初始化，以及剩余的钱数如何继续运作，也就是如果当前硬币用完，怎么样使用另一种硬币等等问题，最后，经查阅资料，艰难地捋清思路，所以要学好算法，逻辑思维要清晰