第二十六章 自动售货机 (第2/2页)

对于这一类问题，最好最高效的方法是动态规划求解，但使用递归蛮力求解，在小数据范围内也是可以的。
　　
　　假如售货机内已有1元钱币3个，5元钱币5个，20元钱币1个。
　　
　　我要购买3元的雪碧一瓶，并投进去了一张20元纸币，那么我得找零17元。
　　
　　先看能用于找零的有什么样的钱币，20元的肯定排除，因为它大于17，售货机可不干亏本买卖！
　　
　　然后，我们看3个1元钱币和5个5元钱币能不能产生找零17元的结果？
　　
　　答案是肯定的，3个5元钱币和2个1元钱币就能够组成17。
　　
　　这就是递归匹配的过程，不过具体实现上面，很多地方可以优化，用来提高效率。
　　
　　“真的是好麻烦啊”，杨成擦了一把汗，在路灯的照耀下挥汗如雨。
　　
　　早知道喝瓶雪碧解解渴这样的简单要求居然要先写个多小时的代码，还不如把自己送到海南喝点纯正的椰子汁。
　　
　　“哟西，终于搞定了”，杨成不愧是有毅力的程序员。
　　
　　“叮！恭喜您完成了自动售货机的相关任务！”
　　
　　“当前积分55分，击败了全球27%的玩家，请您再接再厉！”
　　
　　“咕噜噜”，从自动售货机的出货口滚落下来一瓶冰镇的雪碧，还有一张小小的便笺。
　　
　　便笺上面写着一行娟秀的字迹——“请慢用^_^”