超市111

证明一下反悔贪心正确性

假设我们当前考虑的第$i$个物品，前面$i-1$个物品已经是满足题意的情况下尽量大的$t$个物品了

注意由于这是反悔贪心，所以别从全局的决策包容性的角度考虑，因为之前做出的选择可能根本不是全局最优解；我们应该考虑这种决策之后，对于前$i$个物品来说，一定是尽量大的$t$个物品

如果$i$可以直接放入，没啥好说的肯定放入，是尽量大的$t$个物品

如果$i$不可以直接放入，那么就说明现在$t$个物品已经把前$t$天占满了。假设存在另一种包含$i$的物品价值总和更大的方案$B$（$B$的物品总价值大于蓝书上说的用第$i$个物品取代价值最小的物品的方案$A$的物品总价值），那么这种方案中，$i$一定是放在第$t$天的（注意按照天数从小到大排序了，所以也可以认为这个方案中过期天数越大的放在越后面），我们拿掉第$i$个物品，然后将前$t-1$个物品依次往后移动一天，直到某一个物品不能往后移动（不然就过期了），设这个物品是前$t-1$个物品中的第$j$个物品，那么考虑我们现在堆里面的$t$个物品中（注意，这$t$个物品是没有放入第$i$个物品的时候的物品，也就是前面$i-1$个物品满足题意的情况下利润尽量大的$t$个物品）（注意虽然堆是按照价值排序的，但是下面的分析也是认为按照过期天数升序排序），我们先将堆中$[j+2,t]$的物品和这个方案中$[j+2,t]$的物品进行一一对应（一模一样的物体才可以对应），就像下面一样

注意由于方案中的物品按照了过期天数排序的，所以说方案中$[1,j]$物品是不可能有任何一个为堆中$[j+1,t]$物品；如果对应过程中，堆中物品$x$有一个无法对应，那么把堆中的这个物品$x$移到方案的空位上会得到一个更大的结果（这是因为堆中这个物品显然在方案中没有出现过；我们最开始有$A$的总价值小于$B$的总价值，也就是说$A$去掉第$i$个物品的总价值小于$B$去掉第$i$个物品的总价值，而$A$去掉第$i$个物品再添加上被第$i$物品替代的那一个物品就变成了上面分析中所说的“堆”的物品，也即前面$i-1$个物品满足题意的情况下利润尽量大的$t$个物品，$B$去掉第$i$个物品再加上$x$的总价值却大于了前面$i-1$个物品满足题意的情况下利润尽量大的$t$个物品，这显然矛盾）；否则都可以对应，那么在堆中的第$j+1$个物品直接放到空位上即可，仍然导出矛盾

原文地址：https://blog.csdn.net/dingxingdi/article/details/140621002

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！