硬币兑换问题(算法设计)

兑换硬币不同面额硬币，个数不限￥0.25、0.1、0.05、0.01兑换钱数￥0.63目标：用于兑换的硬币个数最少穷举所有可能性按面值从大到小选择硬币兑换0.63=2*0.25+1*0.1+3*0.01兑换硬币按面值从大到小选择硬币！选用的硬币面额越大，需要用于兑换的硬币个数就越少这就是贪心策略！硬币兑换的贪心算法//需兑换钱数＝a;//可用硬币面额集合＝d;while(兑换未完成){

选出当前可用的最大面额x;

用面额x执行兑换：使用数量＝c、兑换金额＝e;

累计硬币使用总量sum=sum+c;}每种面额只考察了一次，效率高！如何知道兑换未完成？硬币兑换的贪心算法//需兑换钱数＝a;//可用硬币面额集合＝d;while(剩余金额>0

){

选出当前可用的最大面额x;

用面额x执行兑换：使用数量＝c、兑换金额＝e;累计硬币使用总量sum=sum+c;

剩余金额=剩余金额-e;}剩余金额如何表示？面额集合如何表示？兑换量如何计算？兑换方案如何表示？兑换硬币的贪心算法实现输入：d[]：面额数组(值：大小)，n：面额种数，a：需兑换金额输出：最少的兑换硬币个数intgreedyChange(intd[],intn,inta){inti=1;intsum=0;while(a>0){intc=a/d[i];//计算面额为d[i]的硬币兑换量(整除)sum=sum+c;//累计硬币使用总量

a=a–c*d[i];//计算剩余金额i=i+1;//考察下一面额}returnsum;//结果：用于兑换的硬币总数}每种硬币的具体兑换量？兑换硬币的贪心算法实现intgreedyChange(intd[],intn,inta){inti=1;intsum=0;while(a>0){intc=a/d[i];

a=a–c*d[i];

sum=sum+c;i=i+1;}returnsum;}d[]={25,10,5,1}，a=631)i=1：a=63>0c=a/d[1]=2a=a–c*d[1]=13，sum=22)i=2：a=13>0c=a/d[2]=1a=a–c*d[2]=3，sum=33)i=3：a=3>0

c=a/d[3]=0，d[3]=5a=a–c*d[3]=3，sum=34)i=4：a=3>0c=a/d[4]=3a=a–c*d[4]=0，sum=65)i=5：a=0，算法终止兑换硬币贪心策略效率高每种面额只处理一次，无需考察不同的面额组合动态规划：系统考察所有组合有局限！面额：￥0.11,0.05,0.01，兑换：￥0.15还能使用贪心策略吗？贪心算法的基本思想总是作出在当前看来最好的选择在某种意义上的局部最优选择，不从整体最优考虑希望得到的最终结果整体最优单源最短路经问题，最小生成树问题等不一定总能得到整体最优解这时的结果是最优解的很好近似可行、较优解硬币兑换的动态规划算法动态规划对每种面额检查其选与不选的情况下，兑换是否最优！如何应用动态规划？回顾动态规划的步骤证明问题满足最优子结构性质定义与最优解相关的最优值推导最优值计算递归式根据计算递归式设计算法，计算最优值，同时保存最优解相关信息根据上一步得到的信息，构造最优解硬币兑换的动态规划算法动态规划的步骤证明问题满足最优子结构性质证明贪心算法正确性时，已经得证定义与最优解相关的最优值推导最优值计算递归式怎么做？提示：参照0-1背包的动态规划算法m(i,j)可选物品i,i+1,……,n，背包容量jc(i,j)可选面额d[i],d[i+1],……,d[n]，需兑换金额j硬币兑换的动态规划算法假定面额数组：d[1]>d[2]>…>d[n]=1需兑换金额a最优值c(i,j)可选面额d[i],d[i+1],……,d[n]，需兑换金额j1≤i≤n，0≤j≤a递归计算式当d[i]＞j时，c(i,j)=c(i+1,j)当d[i]≤

j时，c(i,j)=min{c(i+1,j),j/d[i]+c(i,jmodd[i])}硬币兑换的动态规划算法dynamicChange(d[],n,a,c[][]){ for(j=0;j<=a;j++)c[n][j]=j;//初始化：面额d[n] for(i=n–1;j>=1;j--)//逐行向上for(j=0;j<=a;j++){if(d[i]>j)//面额d[i]超过金额jc[i][j]=c[i+1][j];else{if(c[i+1][j]<j/d[i]+c[i][j%d[i]])//不选面额d[i]更小c[i][j]=c[i+1][j];elsec[i][j]=j/d[i]+c[i][j%d[i]];//选面额d[i]更小}}}硬币兑换动态规划算法实例d[1]=11,d[2]=5,d