背包问题

背包问题

对背包问题状态转移方程的一个证明。

for (int i=1;i<=n;i++){
    for (int j=m;j>=v[i];j--){
      f[j]=max(f[j],f[j-v[i]]+1);
    }
  }

使用数学归纳法。

首先考虑只有一个物品的情况。这种情况很简单，选一定比不选好。

其次，假设我们已经得到了有n个物品情况的最优解，我们来尝试推出有n+1个物品时的最优解。

对于任意一个合法的j，此时无非只有两种决策，选或不选，依次考虑这两种情况即可。所以算法得到的一定是最优解。

T1:

一共有n件食材，每件食材有三个属性，ai，bi和ci，如果在t时刻完成第i样食材则得到ai-t*bi的美味指数，用第i件食材做饭要花去ci的时间。

众所周知，gw的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大

可以看到，在本题中食材的价值是一个随着t变化的函数。

应该意识到在最终的答案中b越大的越应该放前面，因为这样才能使整体的价值最大。

在最终的答案中c越大的越应该放后面，因为这样才能使那些c大的食材不至于“阻塞”后面的食材。

b和c一起似乎可以确定某种顺序，我们来考虑从数学上计算一下。 \[ 考虑两个相邻的对象。\\ S_1 = a_i-t_0*b_i\\ S_2 = a_{i+1}-(t_0+c_i)*b_{i+1}\\ 则它们的价值和为\\ T_1 = (a_i+a_{i+1})-(b_i+b_{i+1})*t_0-c_i*b_{i+1}\\ 而如果将这两个对象交换。\\ S_1 = a_i - (t_0+c_{i+1})*b_i\\ S_2 = a_{i+1} -t_0*b_{i+1}\\ 则此时价值和为\\ T_2 = (a_i+a_{i+1})-(b_i+b_{i+1})*t_0-c_{i+1}*b_i\\ 易得T_1>T_2的充分必要条件为\\ c_i*b_{i+1} < c_{i+1}*b_i \] 由冒泡排序的思想，这必然可以确定一个顺序。即对于任意的两个物品x，y。如果有b[x]*c[y]<b[y]*c[x]则在最终的答案中x一定在y的前面。

那么在DP时按这个顺序枚举是否就能保证答案的正确性呢？

答案是肯定的。

我们来考虑一下背包DP中，物品种类的枚举顺序的意义是什么。因为在本题中时间是一维状态，为什么枚举的顺序对它有影响呢？

事实上，首先，如果不按这个顺序枚举，是一定无法得到最优解的，只有按这个顺序枚举，才可能得到最优解。也就是说这个顺序是最优解的必要条件。

因为背包DP本质上也是一种刷表法（这一点可以用滚动数组优化之前的朴素方法来考虑），是从上一个最优解转移到下一个多了一种物品选择的最优解。而上一个最优解中可能已经选了一些物品，而这可能破坏掉最优解的必要条件。

但如果我们按排好序后的枚举，则不会破坏必要条件，且按照前面对背包DP正确性的证明，它考虑了每一种合法的情况，因而一定可以得到最优解。