算法作业3 王宏志

作业 3

学生： 周宇 学号： 1093710219

考虑找钱问题，即用最小个数的硬币找n分钱，设每种面值的硬币个数无限。 (1) 设计贪心算法求解硬币面值为c0,c1,…,ck (其中c和k都是大于1的整数) 的找钱 问题并证明其最优性;

算法： 伪代码：

Procedure GREEDY_CHANGE(n) Begin D[0] =1;

For I = 1 to k do D[i] = D[i-1]*c For I = k downto 1 do Begin

S[i ] = n div d[i] n = n mod d[i] end s[0] = n end;

{GREEDY_CHANGE} 最优子结构性质

设s[i], i = 0..k 是找钱问题的一个最优解。则容易验证，s’[i] = s[i], 0 ≦i≦k 且i≠j , s’[j]= s[j]-1,是当s[j]>0时，n-c2的一个最优解。 贪心选择性质 设s[j],I = 0..k，是找钱n问题的一个最优解。则s[i]≦c-1,i=0..k-1.事实上，若存在0≦j≦k-1是s[i]≥c,则用1枚面值为cj+1的硬币去替换c枚面值为cj的硬币，使所用的硬币个数减少c-1枚。由于c>1，故至少减少1枚硬币，从而s[i],i=0..k不是最优解。 当n≥ck时，有s[k]>0。因若不然则

。由s[i]≦c-1,i=0..k-1可知

这是一个矛盾。

(2) 给出不超过5种硬币面值，单个硬币面值不超过10，使得对于这些硬币面值， 贪心算法无法给出找钱问题的最优解，要求证明此结论;

取硬币面值集合c[0..5]={1,3,5,7,8,10}。当n = 12时，用贪心算法找到的解为10+1+1而最优解为7+5.因此，对于这个硬币面集集合，用贪心算法得不到最优解。 (3) 给出贪心法能够求得找钱问题最优解的硬币面值的充分条件和必要条件； 由（1）中贪心选择性证明，同理可知

当

,0≦i≦k-1时，s[i]>0.

即贪心算法所能求得找钱问题最优解的充分必要条件为

,0≦i≦k-1。

(4) 设计搜索算法并基于爬山法和分支界限法对其进行优化，使其对于任意硬币 面值集合都能得到找钱问题的最优解。要求写出算法执行过程，利用问题(2)答 案中面值的硬币，求出用最小个数的硬币找40分钱方案，无需写出伪代码。 比如硬币面值1,10,25找40分钱。

所以方案是4枚10分的硬币。

本文来源：https://www.bwwdw.com/article/1iot.html