動态規劃——背包問題【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 ] ]