利用贪心算法解决购物找零问题（最小化硬币数量）

简介：
本篇文章探讨了如何运用贪心算法来优化购物时找零的过程，重点在于通过选择最少数量和适当面值的硬币组合实现找零，以达到找零效率的最大化。这种方法在处理特定货币系统中能够有效减少交易过程中的硬币使用量，简化交易步骤并提高服务效率。 硬币找钱问题描述：设有6种不同面值的硬币，各硬币的面值分别为5分、1角、2角、5角、1元及2元。现要用这些面值的硬币来购物和找零。在一次购物中规定了可以使用的各种面值的硬币个数，并假定商店里有足够的每种硬币供使用，顾客也可以用多种方式支付。题目要求是，在给定的各种不同面额的硬币数量及付款金额的情况下，计算出最少需要多少枚硬币来完成交易。 例如：一次购物需付0.55元但没有提供5角的硬币，则只能通过两种方案中的一个来进行： - 使用2*2角+1角+5分共4个硬币； - 或者付出1元，找回4角5分同样需要使用到4枚硬币； 然而如果顾客选择支付1.05元（即一枚一元和一枚五分的硬币），商店则可以找还给顾客五个一角的硬币，并且只需要用到了3个硬币。这是在所有方案中所使用的最少数量。 任务是：对于每一组输入数据，计算出完成交易所需的最小硬币数目；如果无法实现该交易，则输出impossible。 输入样例： 2 4 2 2 1 0 0.95 2 4 2 0 1 0 0.55 0 0 0 0 0 结束（注意，以六个零表示数据的结尾） 输出样例： 对于每组输入应对应一行最小硬币个数的结果； 例如： 2 3 若无法完成交易则显示impossible。