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

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

2、面額 x 執(zhí)行兌換：使用數(shù)量c、兌換金額e ; 累計硬幣使用總量 sum = sum + c ; 每種面額只考察了一次，效率高！每種面額只考察了一次，效率高！如何知道兌換未完成？CS-SWPU /需兌換錢數(shù)a; /可用硬幣面額集合d; while ( 剩余金額剩余金額0 ) 選出當(dāng)前可用的最大面額 x ; 用面額 x 執(zhí)行兌換：使用數(shù)量c、兌換金額e ; 累計硬幣使用總量 sum = sum + c ; 剩余金額剩余金額 = 剩余金額剩余金額 - e; 剩余金額如何表示？面額集合如何表示？兌換量如何計算？兌換方案如何表示？兌換方案如何表示？CS-SWPU輸入：d ：面額數(shù)組(值：大小)，n：面

3、額種數(shù)，a：需兌換金額輸出：最少的兌換硬幣個數(shù)int greedyChange (int d , int n, int a) int i = 1; int sum = 0 ; while ( a 0 ) int c = a / di ; /計算面額為 di 的硬幣兌換量 (整除) sum = sum + c ; /累計硬幣使用總量 a = a c*di ; /計算剩余金額 i = i + 1; /考察下一面額 return sum ; / 結(jié)果：用于兌換的硬幣總數(shù)每種硬幣的具體兌換量？CS-SWPUint greedyChange (int d ,int n,int a) int i = 1;

4、 int sum = 0 ; while ( a 0 ) int c = a / di ; a = a c*di ; sum = sum + c ; i = i + 1; return sum ;d = 25, 10, 5, 1，a = 631) i=1：a = 63 0 c = a / d1 = 2 a = a c * d1= 13，sum = 22) i =2：a = 13 0 c = a / d2 =1 a = a c * d2 = 3，sum = 33) i=3：a = 3 0 c = a / d3 = 0，d3 = 5 a = a c * d3 = 3，sum = 34) i=4：a

5、 = 3 0 c = a / d4 = 3 a = a c * d4 = 0，sum = 65) i=5：a=0，算法終止CS-SWPUn貪心策略q效率高n每種面額只處理一次，無需考察不同的面額組合q動態(tài)規(guī)劃：系統(tǒng)考察所有組合q有局限！有局限！n面額：￥0.11, 0.05, 0.01，兌換： ￥ 0.15q還能使用貪心策略嗎？還能使用貪心策略嗎？CS-SWPUn總是作出在當(dāng)前看來最好的選擇q在某種意義上的局部最優(yōu)選擇，不從整體最優(yōu)考慮n希望得到的最終結(jié)果整體最優(yōu)q單源最短路經(jīng)問題，最小生成樹問題等n不一定總能得到整體最優(yōu)解不一定總能得到整體最優(yōu)解q這時的結(jié)果是最優(yōu)解的很好近似這時的結(jié)果是最優(yōu)

6、解的很好近似n可行、較優(yōu)解可行、較優(yōu)解CS-SWPUn動態(tài)規(guī)劃q對每種面額檢查其選與不選的情況下，兌換是否最優(yōu)！q如何應(yīng)用動態(tài)規(guī)劃？n回顧動態(tài)規(guī)劃的步驟q證明問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)q定義與最優(yōu)解相關(guān)的最優(yōu)值q推導(dǎo)最優(yōu)值計算遞歸式q根據(jù)計算遞歸式設(shè)計算法，計算最優(yōu)值，同時保存最優(yōu)解相關(guān)信息q根據(jù)上一步得到的信息，構(gòu)造最優(yōu)解CS-SWPUn動態(tài)規(guī)劃的步驟q證明問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)n證明貪心算法正確性時，已經(jīng)得證q定義與最優(yōu)解相關(guān)的最優(yōu)值q推導(dǎo)最優(yōu)值計算遞歸式n怎么做？n提示：參照0-1背包的動態(tài)規(guī)劃算法qm(i, j) 可選物品 i, i +1, , n，背包容量 jqc (i, j) 可選面額

7、可選面額 di, di +1, , dn，需兌換金額，需兌換金額 jCS-SWPUn假定q面額數(shù)組：d1d2dn=1q需兌換金額 an最優(yōu)值c (i, j)q可選面額 di, di +1, , dn，需兌換金額 jq1 i n，0 j an遞歸計算式q當(dāng)di j 時，c (i, j) = c ( i+1, j )q當(dāng)di j 時，c (i, j) = min c(i+1, j), j / di + c(i, j mod di) CS-SWPUdynamicChange(d , n, a, c ) for (j=0; j=1; j-) /逐行向上 for (j=0; j j ) /面額di 超過金額 j cij = ci + 1j; else if ( ci+1j j/di + ci j % di ) /不選面額di更小 cij = ci + 1j; else cij = j/di + ci j % di ; /選