硬币找钱问题
与网易博客http://yixiong89921.blog.163.com/blog/static/132537788201137105357406/同步
问题描述

设有6种不同面值的硬币，各硬币的面值分别为5分，1角，2角，5角，1元，2元。现要用这些面值的硬币来购物和找钱。购物时规定了可以使用的各种面值的硬币个数。

假定商店里各面值的硬币有足够多，顾客也可用多种方式支付。在1次购物中希望使用最少硬币个数。例如，1次购物需要付款0.55元，没有5角的硬币，只好用2*20+10+5共4枚硬币来付款。如果付出1元，找回4角5分，同样需要4枚硬币。但是如果付出1.05元（1枚1元和1枚5分），找回5角，只需要3枚硬币。这个方案用的硬币个数最少。

您的任务：对于给定的各种面值的硬币个数和付款金额，计算使用硬币个数最少的交易方案。

输入

有若干行测试数据。每一行有6个整数a5、a4、a3、a2、a1、a0和1个有2位小数的实数money，分别表示5分，1角，2角，5角，1元，2元面值的硬币个数和付款金额，money<=1000。文件以6个0结束（不必处理）。

输出

对每一行测试数据，一行输出最少硬币个数。如果不可能完成交易，则输出“impossible”。

输入样例

2 4 2 2 1 0 0.95

2 4 2 0 1 0 0.55

0 0 0 0 0 0

输出样例

2

3

具体代码稍后放出。

4月12日更新代码，不好意思，CSDN的审核可能比较久……现在才出来http://download.csdn.net/source/3167555

其核心思想为消费者硬币数量有限，商店的硬币无限。因此问题可以用以下公式来描述

1、Min(消费者支付金币数量+商店找零金币数量)；

2、支付值-找零值=商品值

寻找上面两个问题的最优解。

现在说说贪心算法的灵魂所在，下面会介绍为什么是这样。

这里所用的贪心算法为：MAX（消费者拥有的硬币面值-商店拥有的硬币面值）优先使用。

例如消费者拥有面值为2元的硬币，商店拥有5分的硬币，因此max=2元-5分=195分。那么上面所有的组合情况为

2元（不找零的情况）,2元-5分,2元-1角,......，5分(不找零的情况)

现在假如我购买的商品是2元，那么用上面的组合中使用2元优先，只用1个硬币即可；假如商品是2元9角5分，我们从上面的序列中使用贪心算法来选择，那么就是一枚2元的硬币优先，那么9毛5如何处理呢，因为上面的序列中存在1元-5分存在的情况，这是能够使用的最大币值（贪心）,就用它了，那么它是2枚硬币，即支付1元找零5分，总共用了3枚硬币。

接下来验证这个算法的贪心选择性和最优子结构性质，证明贪心算法可以获得最优解

贪心选择性：用贪心策略的选择替代原来的选择，如果能获得更优解或同优解，那么贪心策略就可以获得最优解。

我们把相应的序列列出来（用“分”来表示）：

C[]={200,195,190,180,150,100,95,90,80,50,45,40,30,20,15,10,5}；（除红色外其它面值都由两硬币之差构成）

证明这个序列具有贪心选择性质即可，这里我们先用一个简单的例子来证明

c[]={10,5,2,1},这里，c[i]的出现次数最多为｛n，1,2,1｝，这样才能得到最优解，因为面值为1的次数为2时，可以用一个面值为2的来代替，硬币使用数就少了，那么就可以获得更优解。面值为2的硬币只能选用2个，若选用了3个，可以用1枚面值为5和一枚面值为1的硬币来代替。概括来讲，就是说如果c[i]超过一定数量，可以用更少的c[i-1]来代替，因此，我们优先选择大的面值的话，就会用更少的硬币数，因此满足贪心选择性质。

这里回归到我们问题的序列C[]，容易看出C[i]总可以用更大的C[i-1]或者配合一些小币值来代替，但是数量<=C[i]的使用数量，因此满足贪心选择性质。当然这过程当中要考虑消费者硬币是否足够的问题

最优子结构性质证明：

设s[i]为各硬币使用数量，S[i]是商品价格为n时的最优解，硬币数为K，现在设某面值的硬币数量减一：S[j]=S[j]-1;则新的S[i]是n-c[j]的最优解,硬币数为k-1，否则，设T[i]是n-c[j]的最优解，硬币数为m，即m<k-1;那么对于n来说，T[i]的硬币数加1应该是最少的硬币数，即m+1<k-1+1=k，与k是最少硬币数矛盾，故问题满足最优子结构性质。

伪代码这里就不写了，如果是软院的同学~还是自己认真写一下吧~我的代码在4月8号公布~也就是明天,给以后不懂的同学参考吧，基本上没什么bug了。

阅读更多

更多精彩内容