“满减优惠”问题

题目描述

    某商店打折促销，满20减5元，现有商品6件，价格分别为P{5,10,13,9,6}，问如何选择商品既获得满减优惠，又可花费最少？

思路分析

    这个问题本质是一个"01背包"问题。记满减优惠的界限为gate，如果我们购买所有商品，那么花费totalCost=Σ(Pi)，如果totalCost<gate，那么无法获得满减优惠，反之则可以获得满减优惠。记gap=totalCost-gate，那我们的问题就转化成，如果选择商品在总价值sum不超过gap的情况下使得sum最大。这就是一个典型的“01背包问题”了，代码还请大家自己试着实现！