“5如果投入了售货机不支持的钱币类型，原路返回无效的钱币”。

“6如果要找零，尽可能从大额的纸币开始，比方说，要找25块钱，退回的结果是1张20块和1张5块，而不是2张10块的和1张5块”。

“7如果售货机已有的钱币无法全额找零，那么尽可能接近地找零，但售货机是不能吃亏的！”

“这是个背包问题啊”，杨成挠了挠头。

最后一条描述说明了问题的性质。

背包问题可以描述为：给定一组物品，每种物品都有自己的价格，在限定的总价值内，我们如何选择，才能使得物品的总价格最高。

对于这一类问题，最好最高效的方法是动态规划求解，但使用递归蛮力求解，在小数据范围内也是可以的。

假如售货机内已有1元钱币3个，5元钱币5个，20元钱币1个。

我要购买3元的雪碧一瓶，并投进去了一张20元纸币，那么我得找零17元。

先看能用于找零的有什么样的钱币，20元的肯定排除，因为它大于17，售货机可不干亏本买卖！