关于饮料供应问题的贪心算法
个人感觉饮料供应问题是符合贪心选择性的
VolumeTotalCountHappiness2^0 TC0_0 H0_0 2^0 TC0_1 H0_1 ... ... ... 2^0 TC0_n0 H0_n0 2^1 TC1_0 H1_0 ... ... ... 2^M TCM_0 HM_0 ... ... ...
如上表，我们有n0中容量为2^0的饮料，它们的数量和满意度分别为(TC0_0,H0_0)，(TC0_1,H0_1)，......假设最大容量为2^M。
贪心算法：
如果V%(2^1)!=0，那么我们购买2^0容量的饮料至少一瓶，使用贪心规则，购买满意度最高的一瓶。除去这个我们还需要购买(V-2^0)的饮料即可。如果(V-2^0)%(2^2)!=0，那么我们需要购买2^1容量的饮料至少一瓶或者容量为2^0的饮料至少两瓶，当然，我们选择满意度最高的。依次类推，即可达到冰箱容积一定条件下的满意度最高。
贪心选择性的正确性证明(非正式)：对于V%(2^1)!=0时，如果我们没有选择满意度最高的2^0容量的饮料一瓶，假设选择了满意度为H0_k(H0_k<H0_n0)的饮料。分以下三种情况考虑
1、在当前最优解中没有满意度为H0_n0容量为2^0的饮料，那么显然将先前选择的满意度为H0_k的饮料替换成满意度为H0_n0的饮料后，满意度又得到了提高。这与当前满意度最高矛盾。
2、在当前最优解中有满意度为H0_n0容量为2^0的饮料，而且数量刚好为TC0_n0，并且无其他容量为2^0的饮料。那么将先前选择的满意度为H0_k的饮料替换成满意度为H0_(n0-1)的饮料后，满意度不小于当前满意度(H0_(n0-1)>=H0_k)。替换后的结果等同于在刚开始时选择满意度为H0_n0的饮料一瓶，在后面将满意度为H0_(n0-1)的饮料作为对满意度为H0_0饮料的补充。
3、在当前最优解中有满意度为H0_n0容量为2^0的饮料，而且数量等于TC0_n0，且还有满意度为H0_(n0-1)的饮料不足TC0_(n0-1)。那么将先前选择的满意度为H0_k的饮料替换成满意度为H0_(n0-1)的饮料后，满意度不小于当前满意度(H0_(n0-1)>=H0_k)。替换后的结果等同于在刚开始时选择满意度为H0_n0的饮料一瓶，在后面将满意度为H0_(n0-1)的饮料作为对满意度为H0_0饮料的补充。
思维方式：最优解中要么没有容量为2^0的类型，如果有那么必然以满意度降序的方式加入。求余操作正是保证了容量为2^0的饮料的存在必然性。对于容量为2^1、2^2、...、2^M的同理。
