找硬币问题

算法导论上第16-1问题

 

考虑用最少的硬币数找n分钱的问题，假设每个硬币的值都是整数。

a）请给出一种贪心算法，使得所换的硬币包括一角的，五分的，二角五分的合一分的。证明所给出的算法能产生最优解。

b）假设可换的硬币单位是c的幂，也就是c⁰,c¹, ..., c^k  其中整数c>1, k>=1.证明贪心算法总可以产生一个最优解。

c） 请给出一组是贪心算法不能产生最优解的的硬币集合。说给集合应该包括一分，以便保证对任意n值都有解。

d）设计O(nk)时间的算法，能够对任意k种不同单位组合的硬币集合进行找换，假设其中一种硬币单位是一分。

 

先证明问题具有最优子结构。假设对找n分前有最优解，而且最优解中使用了面值c的硬币，最优解使用了k个硬币。那么，这个最优解包含了对于找n-c分钱的最优解。显然，n-c分钱中使用了k-1个硬币。如果n-c分钱还有一个解使用了比k-1少的硬币，那么使用这个解可以为找n分钱产生小于k个硬币的解。与假设矛盾。

 

对于有些情况下，贪心算法可能不能产生最优解。比如硬币面值1,10,25.找30分钱，最优解是3*10，而贪心的情况下产生的解是1*5+25.

问题b可以作为一个结论：假设可换的硬币单位是c的幂，也就是c⁰,c¹, ..., c^k, 其中整数c>1, k>=1, 这种情况下贪心算法可以产生最优解。

问题的证明用到了引理：对于i=0,1,..., k, 设a_i是找n分钱的最优解中面值cⁱ 的数量。那么对i=0,1,...,k-1，有a_i<c.

证明：假设ai>=c，对于0<=i<k. 则可以改进最优解通过增加一个面值cⁱ⁺¹的硬币和减少c个面值cⁱ的硬币，这样找零钱的总数不变，但减少了c-1个硬币。于是，这个比最优解还要优化，矛盾。

 

然后证明问题具有贪心选择性质，即贪心选择具有最优解。这里证明不用贪心选择不能产生最优解。设j=max{0<=i<=k: cⁱ<=n}.所以贪心解法会使用至少一个面值c^j的硬币，考虑非贪心选择的解，不使用面值c^j或更高的硬币。设非贪心的解使用a_i数量的面值cⁱ的硬币，对i=0,1, ... , j-1. 所以有a₀c⁰+a₁c¹+ ... +a_j-1c^j-1=n.

因为n>=c^j, 所以上式左边大于等于 c^j. 现在假设这种非贪心选择的解是最优的，由引理a_i<c，上式左边

a₀c⁰+a₁c¹+ ... +a_j-1c^j-1  <= (c-1)c⁰+(c-1)c¹+ ... +(c-1)c^j-1 =(c-1)(1+c+...+c^j-1)=(c-1)(c^j-1)/(c-1)=(c^j-1)<c^j

与上面推出的左边大于等于c^j矛盾。所以可以得到非贪心选择不能产生最优解。

贪心选择的话，问题的复杂度是O(k).K是硬币的个数。假设int a[k+1]是每个面值c⁰,c¹, ..., c^k使用的数量。

for(int i=k;i>=0;i--)

{

   a[i]=n/cⁱ;

   n%=cⁱ;

}

所以如果问题是这种情况，可以直接用贪心而且问题的解确实是最优的。

 

问题d更一般，设计O(nk)时间的算法，能够对任意k种不同单位组合的硬币集合进行找换，假设其中一种硬币单位是一分。

上面已经说明问题具有最优子结构，可以用动态规划求解最优的找零钱的解。

假设c[j]是找j分钱最少的硬币数。硬币的面值是d₁,d₂,...,d_k.由于存在一分钱，所以对j分钱总是存在可以找的零钱。

可以写出递推的式子：

c_j=    0,  if j<=0

c_j=    1+ min{c[j-d_i]}, 1<=i<=k  if j>1

 

写了一个完整的代码，并有输出找钱方案的。测试例子就是上面给出的反例。对25，10，1分钱，找30分钱。

 

 

此外，还有一个找硬币共有多少种解的问题，下次在写吧。