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

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

2、面额 x 执行兑换：使用数量c、兑换金额e ; 累计硬币使用总量 sum = sum + c ; 每种面额只考察了一次，效率高！每种面额只考察了一次，效率高！如何知道兑换未完成？CS-SWPU /需兑换钱数a; /可用硬币面额集合d; while ( 剩余金额剩余金额0 ) 选出当前可用的最大面额 x ; 用面额 x 执行兑换：使用数量c、兑换金额e ; 累计硬币使用总量 sum = sum + c ; 剩余金额剩余金额 = 剩余金额剩余金额 - e; 剩余金额如何表示？面额集合如何表示？兑换量如何计算？兑换方案如何表示？兑换方案如何表示？CS-SWPU输入：d ：面额数组(值：大小)，n：面

3、额种数，a：需兑换金额输出：最少的兑换硬币个数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 ; / 结果：用于兑换的硬币总数每种硬币的具体兑换量？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动态规划：系统考察所有组合q有局限！有局限！n面额：￥0.11, 0.05, 0.01，兑换： ￥ 0.15q还能使用贪心策略吗？还能使用贪心策略吗？CS-SWPUn总是作出在当前看来最好的选择q在某种意义上的局部最优选择，不从整体最优考虑n希望得到的最终结果整体最优q单源最短路经问题，最小生成树问题等n不一定总能得到整体最优解不一定总能得到整体最优解q这时的结果是最优解的很好近似这时的结果是最优

6、解的很好近似n可行、较优解可行、较优解CS-SWPUn动态规划q对每种面额检查其选与不选的情况下，兑换是否最优！q如何应用动态规划？n回顾动态规划的步骤q证明问题满足最优子结构性质q定义与最优解相关的最优值q推导最优值计算递归式q根据计算递归式设计算法，计算最优值，同时保存最优解相关信息q根据上一步得到的信息，构造最优解CS-SWPUn动态规划的步骤q证明问题满足最优子结构性质n证明贪心算法正确性时，已经得证q定义与最优解相关的最优值q推导最优值计算递归式n怎么做？n提示：参照0-1背包的动态规划算法qm(i, j) 可选物品 i, i +1, , n，背包容量 jqc (i, j) 可选面额

7、可选面额 di, di +1, , dn，需兑换金额，需兑换金额 jCS-SWPUn假定q面额数组：d1d2dn=1q需兑换金额 an最优值c (i, j)q可选面额 di, di +1, , dn，需兑换金额 jq1 i n，0 j an递归计算式q当di j 时，c (i, j) = c ( i+1, j )q当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 ; /选