关于找硬币的算法问题，请帮帮忙，急。。。

考虑用最少的硬币数来找n分钱的问题，假设每个硬币的值都是整数。
问题1：请给出一个贪心算法，使得所换硬币包括一角的、五分的、二角五分的和一分的。证明所给出的算法能产生最优解。
问题2：假设可换硬币的单位是c的幂，也就是c0,c1,…,ck，其中整数c>1，k>=1。证明贪心算法总可以产生一个最优解。
问题3：请给出一组使贪心算法不能产生最优解的硬币单位集合。所给集合应当包括一分，以便保证对任意n值都有解。
问题4：请给出一种O（nk）时间的算法，它能够对任意k种不同单位的硬币集合进行找换，假设其中一种硬币单位是一分的。

7 个解决方案

#1

问题2：假设可换硬币的单位是c的幂，也就是c的0次方,c的1次方,…,c的k次方，其中整数c>1，k>=1。证明贪心算法总可以产生一个最优解。

#2

问题1：确定是二角五分而不是2.5分？
问题3：对于硬币组合1角、8分、5分、1分，如果要组成13分，贪心算法为1角+3个1分共4枚，实际最优解为8分+5分共2枚
问题4：是O(n^k)还是O(n*k)？

#3

另，问题2的话，用c进制来考虑好了

#4

首先，感谢你关注我的问题，现在再把问题补充一下！

问题1中：那个单位确实是二角五分，当然在现实生活中没有这个面值的钱币，但问题中有。
对于问题2：我还是没有思路，麻烦你再帮帮忙，拜托了！
问题4中：那个是O（n*k）

我一面在看书学习，一面在想办法解决这道题，还希望大家能多多指点！
谢谢！

#5

问题1：首先将n分钱里除以5余数部分换成1分钱的，因为这是迟早要换的，而且只能这么换，多了不行；其次，将剩下的尽量用2角5分的来换，因为2角5分的至少可以换成2个1角的，即每减少一枚2角5分的硬币就至少要增加2枚1角的来代替，划不来；最后剩下的钱就用1角和5分的来凑了，这个简单

#6

问题2：由于硬币都是c的幂，因此可以用c进制来看待这个问题，不妨让c=2方便描述。对于任意n分钱，n的二进制表示假设为……0101，就表示用1枚1分的，1枚4分的，等等来换n分钱，并且这种换法是最优的，因为：首先n除以2的余数部分必须用1分来换，换完之后接下来n除以4的余数部分用2分来换，以此类推，每一步都是可行的，而且在最少硬币数的约束下多换1个都不行，因此这样考虑是最优解

#7

问题4：这里有O（n*k）算法你可以看下：http://www.javaeye.com/topic/320498
      此外这里还有其他一些讨论也可以看下：http://www.javaeye.com/topic/175886?page=6#501439