“我的要求很简单，就是能喝上一罐82年份的雪碧”。
杨成坏坏地笑了。
“好，满足你！”
系统声音刚落，杨成就出现在了一个自动售货机前面。
漆黑的夜晚，明亮的路灯下面，自动售货机散发出微蓝色的光芒，里面一排排的货架盛放着一瓶瓶饮料。
杨成掏出几个硬币，先选中了雪碧下面的按钮，然后把硬币塞进投币口。
估摸着过了好几秒钟，从出货口并没有滚出来饮料。
相反一个便笺飘落了下来。
借着微弱的灯光，杨成拿起便笺一看，上面写着几行小字。
“为自动售货机编写业务逻辑，已知规则如下：”
“1.售货机接收n种纸币或硬币，其中包括1元，5元，10元....”
“2.售货机最开始拥有各种类型钱币的数量都是一定的”。
“3.如果投入的钱币低于商品的价值，那么将钱币原封不动地退回”。
“4.如果投入的钱币等于商品的价值，那么无须找零”。
“5.如果投入了售货机不支持的钱币类型，原路返回无效的钱币”。
“6.如果要找零，尽可能从大额的纸币开始，比方说，要找25块钱，退回的结果是1张20块和1张5块，而不是2张10块的和1张5块”。
“7.如果售货机已有的钱币无法全额找零，那么尽可能接近地找零，但售货机是不能吃亏的！”
“这是个背包问题啊”，杨成挠了挠头。
最后一条描述说明了问题的性质。
背包问题可以描述为：
给定一组物品，每种物品都有自己的价格，在限定的总价值内，我们如何选择，才能使得物品的总价格最高。
对于这一类问题，最好最高效的方法是动态规划求解，但使用递归蛮力求解，在小数据范围内也是可以的。
假如售货机内已有1元钱币3个，5元钱币5个，20元钱币1个。
我要购买3元的雪碧一瓶，并投进去了一张20元纸币，那么我得找零17元。
先看能用于找零的有什么样的钱币，20元的肯定排除，因为它大于17，售货机可不干亏本买卖！
然后，我们看3个1元钱币和5个5元钱币能不能产生找零17元的结果？
答案是肯定的，3个5元钱币和2个1元钱币就能够组成17。
这就是递归匹配的过程，不过具体实现上面，很多地方可以优化，用来提高效率。
“真的是好麻烦啊”，杨成擦了一把汗，在路灯的照耀下挥汗如雨。
早知道喝瓶雪碧解解渴这样的简单要求居然要先写个多小时的代码，还不如把自己送到海南喝点纯正的椰子汁呢！
“哟西，终于搞定了”。
杨成不愧是有毅力的程序员。
“叮！恭喜您完成了自动售货机的相关任务！”
“当前积分55分，击败了全球27%的玩家，请您再接再厉！”
“咕噜噜...”
从自动售货机的出货口滚落下来一瓶冰镇的雪碧，还有一张小小的便笺。
便笺上面写着一行娟秀的字迹。
“请慢用^_^”
杨成坏坏地笑了。
“好，满足你！”
系统声音刚落，杨成就出现在了一个自动售货机前面。
漆黑的夜晚，明亮的路灯下面，自动售货机散发出微蓝色的光芒，里面一排排的货架盛放着一瓶瓶饮料。
杨成掏出几个硬币，先选中了雪碧下面的按钮，然后把硬币塞进投币口。
估摸着过了好几秒钟，从出货口并没有滚出来饮料。
相反一个便笺飘落了下来。
借着微弱的灯光，杨成拿起便笺一看，上面写着几行小字。
“为自动售货机编写业务逻辑，已知规则如下：”
“1.售货机接收n种纸币或硬币，其中包括1元，5元，10元....”
“2.售货机最开始拥有各种类型钱币的数量都是一定的”。
“3.如果投入的钱币低于商品的价值，那么将钱币原封不动地退回”。
“4.如果投入的钱币等于商品的价值，那么无须找零”。
“5.如果投入了售货机不支持的钱币类型，原路返回无效的钱币”。
“6.如果要找零，尽可能从大额的纸币开始，比方说，要找25块钱，退回的结果是1张20块和1张5块，而不是2张10块的和1张5块”。
“7.如果售货机已有的钱币无法全额找零，那么尽可能接近地找零，但售货机是不能吃亏的！”
“这是个背包问题啊”，杨成挠了挠头。
最后一条描述说明了问题的性质。
背包问题可以描述为：
给定一组物品，每种物品都有自己的价格，在限定的总价值内，我们如何选择，才能使得物品的总价格最高。
对于这一类问题，最好最高效的方法是动态规划求解，但使用递归蛮力求解，在小数据范围内也是可以的。
假如售货机内已有1元钱币3个，5元钱币5个，20元钱币1个。
我要购买3元的雪碧一瓶，并投进去了一张20元纸币，那么我得找零17元。
先看能用于找零的有什么样的钱币，20元的肯定排除，因为它大于17，售货机可不干亏本买卖！
然后，我们看3个1元钱币和5个5元钱币能不能产生找零17元的结果？
答案是肯定的，3个5元钱币和2个1元钱币就能够组成17。
这就是递归匹配的过程，不过具体实现上面，很多地方可以优化，用来提高效率。
“真的是好麻烦啊”，杨成擦了一把汗，在路灯的照耀下挥汗如雨。
早知道喝瓶雪碧解解渴这样的简单要求居然要先写个多小时的代码，还不如把自己送到海南喝点纯正的椰子汁呢！
“哟西，终于搞定了”。
杨成不愧是有毅力的程序员。
“叮！恭喜您完成了自动售货机的相关任务！”
“当前积分55分，击败了全球27%的玩家，请您再接再厉！”
“咕噜噜...”
从自动售货机的出货口滚落下来一瓶冰镇的雪碧，还有一张小小的便笺。
便笺上面写着一行娟秀的字迹。
“请慢用^_^”