算法导论上第 16-1 问题 考虑用最少的硬币数找 n 分钱的问题，假设每个硬币的值都是整数。 先证明问题具有最优子结构。假设对找 n 分前有最优解，而且最优解中使用了面值 c 的硬 币，最优解使用了 k 个硬币。那么，这个最优解包含了对于找 n-c 分钱的最优解。显然，n-c 分钱中使用了 k-1 个硬币。如果 n-c 分钱还有一个解使用了比 k-1 少的硬币，那么使用这个 解可以为找 n 分钱产生小于 k 个硬币的解。与假设矛盾。 算法的源代码： #include int main() { freopen("data.out","w",stdout); int money,s1,s2,s3,s4,p,d,n,q,temp; scanf("%d%d%d%d%d",&money,&s1,&s2,&s3,&s4); temp=money; p = money/s1; if (p >0) money -= p*s1; d = money/s2; if (d >0) money -= d*s2; n = money/s3; if (n >0) 

money -= n*s3; q = money/s4; if (temp==(p*s1+d*s2+n*s3+q)) { printf("%d is sum %d\n",s1,p); printf("%d is sum %d\n",s2,d); printf("%d is sum %d\n",s3,n); printf("%d is sum %d\n",s4,q); } else printf("Not enough change\n"); return 0; } 对于有些情况下，贪心算法可能不能产生最优解。比如硬币面值 1,10,25.找 30 分钱，最优 解是 3*10，而贪心的情况下产生的解是 1*5+25. 问题 b 可以作为一个结论：假设可换的硬币单位是 c 的幂，也就是 c0,c1, ..., ck, 其中整数 c>1, k>=1, 这种情况下贪心算法可以产生最优解。 问题的证明用到了引理：对于 i=0,1,..., k, 设 ai 是找 n 分钱的最优解中面值 ci 的数量。那么 对 i=0,1,...,k-1，有 ai=c，对于 0<=i

然后证明问题具有贪心选择性质，即贪心选择具有最优解。这里证明不用贪心选择不能产生 最优解。设 j=max{0<=i<=k: ci<=n}.所以贪心解法会使用至少一个面值 cj 的硬币，考虑非贪 心选择的解，不使用面值 cj 或更高的硬币。设非贪心的解使用 ai 数量的面值 ci 的硬币，对 i=0,1, ... , j-1. 所以有 a0c0+a1c1+ ... +aj-1cj-1=n. 因为 n>=cj, 所以上式左边大于等于 cj. 现在假设这种非贪心选择的解是最优的，由引理 ai=0;i--) { } a[i]=n/ci; n%=ci; 所以如果问题是这种情况，可以直接用贪心而且问题的解确实是最优的。 问题 d 更一般，设计 O(nk)时间的算法，能够对任意 k 种不同单位组合的硬币集合进行找换， 假设其中一种硬币单位是一分。 上面已经说明问题具有最优子结构，可以用动态规划求解最优的找零钱的解。 假设 c[j]是找 j 分钱最少的硬币数。硬币的面值是 d1,d2,...,dk.由于存在一分钱，所以对 j 分钱 总是存在可以找的零钱。 

可以写出递推的式子： cj= 0, if j<=0 cj= 1+ min{c[j-di]}, 1<=i<=k if j>1