动态规划——背包问题【01背包】

问题描述：

有N种物品和一个容量为V的背包，每种物品仅用一次。第i件物品的费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。

例如：

N=5,V=10

         重量   价值

第一个物品： 10     5

第二个物品： 1     4

第三个物品： 2     3

第四个物品： 3     2

第五个物品： 4     1

首先我们考虑贪心策略，选取最大价值物品装入背包，得到的最大价值为：5。

但是正解为10(后四个物品)。所以我们直接来看背包算法。

定义dp[i][j]:选取i个物品，背包容量为j时，所能获得的最大价值。

由于一个物品只能拿一次或者不拿，那么我们分别分析拿还是不拿。

（1）j < w[i]，这时背包容量不足以放下第i件物品，只能不拿dp[i][j] = dp[i-1][j]

（2）j > w[i]，这时背包可以放下第i件物品，但是这时我们需要考虑拿这件物品是否会获得更大价值。

• 如果拿，dp[ i ][ j ] = dp[ i - 1 ][ j - w[ i ] ] + v[ i ]。这里dp[i-1][j-w[i]]指的是因为我们现在要选取第i个物品，那么之前就肯定选取了i-1个物品；既然想让背包容纳这个物品，那么选取之前背包需要留有w[i]的位置。
• 如果不拿，dp[ i ][ j ] = dp[ i - 1 ][ j ]

那么到底拿还是不拿，就需要比较哪个结果更大。

这就是动态规划的思想：在求值的时候考虑之前的状态。综上所述，我们得到了

状态转移方程：

  if(j >= w[i])

    dp[ i ][ j ] = max( dp[ i - 1 ][ j ], dp[ i - 1][ j - w[ i ] ] + v[ i ] );

  else

    dp[ i ][ j ] = dp[ i - 1 ][ j ];

空间压缩

注意到每次求解dp[i][j]值用到了上一行(i-1)的值：dp[i-1][j] 和 dp[i-1][j-w[i]]，考虑用dp[j]来表示之前dp[i][j]的状态。

• 在第 i 次循环开始之前，dp[ j ] = dp[ i -1 ][ j ];（0 <= j <= V）
• 在第 i 次循环结束之后，dp[ j ] = dp[ i ][ j ];（0 <= j <= V）

那么在计算第 i 次循环的dp值时，拿或者不拿的选择变为下列情况：

• 如果放弃物品 i ，即dp[ i ][ j ] = dp[ i - 1][ j ]，dp[ j ]保持不变即可
• 如果选取物品 i ，即dp[ i ][ j ] = dp[ i - 1][ j - w[ i ] ]，很幸运，当前的dp[ j - w[ i ] ]就是dp[ i - 1][ j - w[ i ] ]