硬幣兌換問題(算法設計)

兌換硬幣不同面額硬幣，個數(shù)不限￥0.25、0.1、0.05、0.01兌換錢數(shù)￥0.63目標：用于兌換的硬幣個數(shù)最少窮舉所有可能性按面值從大到小選擇硬幣兌換0.63=2*0.25+1*0.1+3*0.01兌換硬幣按面值從大到小選擇硬幣！選用的硬幣面額越大，需要用于兌換的硬幣個數(shù)就越少這就是貪心策略！硬幣兌換的貪心算法//需兌換錢數(shù)＝a;//可用硬幣面額集合＝d;while(兌換未完成){

選出當前可用的最大面額x;

用面額x執(zhí)行兌換：使用數(shù)量＝c、兌換金額＝e;

累計硬幣使用總量sum=sum+c;}每種面額只考察了一次，效率高！如何知道兌換未完成？硬幣兌換的貪心算法//需兌換錢數(shù)＝a;//可用硬幣面額集合＝d;while(剩余金額>0

){

選出當前可用的最大面額x;

用面額x執(zhí)行兌換：使用數(shù)量＝c、兌換金額＝e;累計硬幣使用總量sum=sum+c;

剩余金額=剩余金額-e;}剩余金額如何表示？面額集合如何表示？兌換量如何計算？兌換方案如何表示？兌換硬幣的貪心算法實現(xiàn)輸入：d[]：面額數(shù)組(值：大小)，n：面額種數(shù)，a：需兌換金額輸出：最少的兌換硬幣個數(shù)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;//結(jié)果：用于兌換的硬幣總數(shù)}每種硬幣的具體兌換量？兌換硬幣的貪心算法實現(xiàn)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，算法終止兌換硬幣貪心策略效率高每種面額只處理一次，無需考察不同的面額組合動態(tài)規(guī)劃：系統(tǒng)考察所有組合有局限！面額：￥0.11,0.05,0.01，兌換：￥0.15還能使用貪心策略嗎？貪心算法的基本思想總是作出在當前看來最好的選擇在某種意義上的局部最優(yōu)選擇，不從整體最優(yōu)考慮希望得到的最終結(jié)果整體最優(yōu)單源最短路經(jīng)問題，最小生成樹問題等不一定總能得到整體最優(yōu)解這時的結(jié)果是最優(yōu)解的很好近似可行、較優(yōu)解硬幣兌換的動態(tài)規(guī)劃算法動態(tài)規(guī)劃對每種面額檢查其選與不選的情況下，兌換是否最優(yōu)！如何應用動態(tài)規(guī)劃？回顧動態(tài)規(guī)劃的步驟證明問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)定義與最優(yōu)解相關(guān)的最優(yōu)值推導最優(yōu)值計算遞歸式根據(jù)計算遞歸式設計算法，計算最優(yōu)值，同時保存最優(yōu)解相關(guān)信息根據(jù)上一步得到的信息，構(gòu)造最優(yōu)解硬幣兌換的動態(tài)規(guī)劃算法動態(tài)規(guī)劃的步驟證明問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)證明貪心算法正確性時，已經(jīng)得證定義與最優(yōu)解相關(guān)的最優(yōu)值推導最優(yōu)值計算遞歸式怎么做？提示：參照0-1背包的動態(tài)規(guī)劃算法m(i,j)可選物品i,i+1,……,n，背包容量jc(i,j)可選面額d[i],d[i+1],……,d[n]，需兌換金額j硬幣兌換的動態(tài)規(guī)劃算法假定面額數(shù)組：d[1]>d[2]>…>d[n]=1需兌換金額a最優(yōu)值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])}硬幣兌換的動態(tài)規(guī)劃算法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]更小}}}硬幣兌換動態(tài)規(guī)劃算法實例d[1]=11,d[2]=5,d