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

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

選出當(dāng)前可用的最大面額x;

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

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

){

選出當(dāng)前可用的最大面額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還能使用貪心策略嗎？貪心算法的基本思想總是作出在當(dāng)前看來最好的選擇在某種意義上的局部最優(yōu)選擇，不從整體最優(yōu)考慮希望得到的最終結(jié)果整體最優(yōu)單源最短路經(jīng)問題，最小生成樹問題等不一定總能得到整體最優(yōu)解這時的結(jié)果是最優(yōu)解的很好近似可行、較優(yōu)解硬幣兌換的動態(tài)規(guī)劃算法動態(tài)規(guī)劃對每種面額檢查其選與不選的情況下，兌換是否最優(yōu)！如何應(yīng)用動態(tài)規(guī)劃？回顧動態(tài)規(guī)劃的步驟證明問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)定義與最優(yōu)解相關(guān)的最優(yōu)值推導(dǎo)最優(yōu)值計算遞歸式根據(jù)計算遞歸式設(shè)計算法，計算最優(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)值推導(dǎo)最優(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āng)d[i]＞j時，c(i,j)=c(i+1,j)當(dāng)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