超市111
证明一下反悔贪心正确性
假设我们当前考虑的第 i i i个物品，前面 i − 1 i-1 i−1个物品已经是满足题意的情况下尽量大的 t t t个物品了
注意由于这是反悔贪心，所以别从全局的决策包容性的角度考虑，因为之前做出的选择可能根本不是全局最优解；我们应该考虑这种决策之后，对于前 i i i个物品来说，一定是尽量大的 t t t个物品
如果 i i i可以直接放入，没啥好说的肯定放入，是尽量大的 t t t个物品
如果 i i i不可以直接放入，那么就说明现在 t t t个物品已经把前 t t t天占满了。假设存在另一种包含 i i i的物品价值总和更大的方案 B B B（ B B B的物品总价值大于蓝书上说的用第 i i i个物品取代价值最小的物品的方案 A A A的物品总价值），那么这种方案中， i i i一定是放在第 t t t天的（注意按照天数从小到大排序了，所以也可以认为这个方案中过期天数越大的放在越后面），我们拿掉第 i i i个物品，然后将前 t − 1 t-1 t−1个物品依次往后移动一天，直到某一个物品不能往后移动（不然就过期了），设这个物品是前 t − 1 t-1 t−1个物品中的第 j j j个物品，那么考虑我们现在堆里面的 t t t个物品中（注意，这 t t t个物品是没有放入第 i i i个物品的时候的物品，也就是前面 i − 1 i-1 i−1个物品满足题意的情况下利润尽量大的 t t t个物品）（注意虽然堆是按照价值排序的，但是下面的分析也是认为按照过期天数升序排序），我们先将堆中 [ j + 2 , t ] [j+2,t] [j+2,t]的物品和这个方案中 [ j + 2 , t ] [j+2,t] [j+2,t]的物品进行一一对应（一模一样的物体才可以对应），就像下面一样
注意由于方案中的物品按照了过期天数排序的，所以说方案中 [ 1 , j ] [1,j] [1,j]物品是不可能有任何一个为堆中 [ j + 1 , t ] [j+1,t] [j+1,t]物品；如果对应过程中，堆中物品 x x x有一个无法对应，那么把堆中的这个物品 x x x移到方案的空位上会得到一个更大的结果（这是因为堆中这个物品显然在方案中没有出现过；我们最开始有 A A A的总价值小于 B B B的总价值，也就是说 A A A去掉第 i i i个物品的总价值小于 B B B去掉第 i i i个物品的总价值，而 A A A去掉第 i i i个物品再添加上被第 i i i物品替代的那一个物品就变成了上面分析中所说的“堆”的物品，也即前面 i − 1 i-1 i−1个物品满足题意的情况下利润尽量大的 t t t个物品， B B B去掉第 i i i个物品再加上 x x x的总价值却大于了前面 i − 1 i-1 i−1个物品满足题意的情况下利润尽量大的 t t t个物品，这显然矛盾）；否则都可以对应，那么在堆中的第 j + 1 j+1 j+1个物品直接放到空位上即可，仍然导出矛盾
原文地址：https://blog.csdn.net/dingxingdi/article/details/140621002
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！