证明一下反悔贪心正确性
假设我们当前考虑的第\(i\)个物品，前面\(i-1\)个物品已经是满足题意的情况下尽量大的\(t\)个物品了
注意由于这是反悔贪心，所以别从全局的决策包容性的角度考虑，因为之前做出的选择可能根本不是全局最优解；我们应该考虑这种决策之后，对于前\(i\)个物品来说，一定是尽量大的\(t\)个物品
如果\(i\)可以直接放入，没啥好说的肯定放入，是尽量大的\(t\)个物品
如果\(i\)不可以直接放入，那么就说明现在\(t\)个物品已经把前\(t\)天占满了。假设存在另一种包含\(i\)的物品价值总和更大的方案，那么这种方案中，\(i\)一定是放在第\(t\)天的（注意按照天数从小到大排序了），我们拿掉第\(i\)个物品，然后将前\(t-1\)个物品依次往后移动一天，直到某一个物品不能往后移动（不然就过期了），设这个物品是前\(t-1\)个物品中的第\(j\)个物品，那么考虑我们现在堆里面的\(t\)个物品中，我们先将堆中\([j+1,t]\)的物品和这个方案中\([j+1,t]\)的物品进行一一对应（一模一样的物体才可以对应），就像下面一样
如果对应过程中，有一个无法对应，那么把堆中的这个物品移到方案的空位上会得到一个更大的结果；否则都可以对应，那么在堆中的第\(j+1\)个物品直接放到空位上即可
标签：方案,那么,放入,物品,超市,对应,贪心 From： https://www.cnblogs.com/dingxingdi/p/18133769