找换硬币
考虑用最少的硬币数来找N分钱的问题，假设每个硬币的值都是整数。
a) 请给出一个贪心算法，使得所换硬币包括一角的，五分的，二角五分的和一分的。证明所给出的算法能产生最优解。
b) 假设可换的硬币的单位是c的幂，也就是c^0,c^1,c^2,c^3……其中整数c>1,k>=1。证明贪心算法总可以产生一个最优解。
c) 请给出一组是贪心算法不能产生最优解的硬币单位集合。所给集合应当包括一分，以便保证对任意n值都有解。
d) 请给出一种O(nk)时间的算法，它能够对任意K种不同单位的硬币集合进行找换，假设其中一种硬币单位是一分的。
解：
a) 找换硬币的贪心算法思想：
（1）将找换集合中的元素进行降序排列,CurrentMax指向首元素；
（2）判断N是否大于找换集合中当前最大元素，如果大于，N=N-CurrentMax；再执行此步骤。如果不大于，则找换集合中的CurrentMax指向下一个元素，执行此步骤。
（3）若N=0，则找到了找换硬币的方法。
算法的源代码：
#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;
}
c) 找换集合的元素如果是{1,3,4}，被找换的元素如果是10 ，那么采用上述方法得到的找换方法是：4，4，1，1。 而最优的方式是：4,3,3。