? 關(guān)于0/1背包問題網(wǎng)上有非常多的博文，在此我謹記錄一下自己的理解。

? 問題表述：有N件物品和一個容量為V的背包。第i件物品的體積是C[i](0<=i<=N-1)，價值是W[i]。求解將哪些物品裝入背包可使價值總和最大。每個物品最多只可以放入背包一次。

? 這個問題的經(jīng)典解法思路如下：

? 我們用f[i][j]表示在考慮前i個物品時體積為j的背包的最大價值，注意，我們并不是把前i個物品全部放入背包，而是考慮i個物品中挑選一些放入背包，使得價值最大的那些情況。

? 首先，我們考慮只有1個物品(第0個)時，容量分別為0,1,...,V的各背包所包含物品的最大價值。很明顯，容量大于等于C[0]的背包的最大價值為W[0]，容量小于C[0]的背包的最大價值為0。

? 然后，我們考慮再來一個(第i個)物品時，容量分別為0,1,...,V的各背包所包含物品的最大價值。對于某個背包，我們有兩種選擇：將該物品放入該背包或者不放入。

? 當我們將該物品放入某個體積為j的背包時，該背包的最大價值為f[i][j-C[i]]+W[i]。當我們不把該物品放入某個體積為j的背包時，該背包的最大價值為f[i-1][j]。所以在考慮前i個物品時，體積為j的背包的最大價值為f[i][j]=max{f[i-1][j],f[i][j-C[i]]+W[i]}.

? 迭代以上步驟，從i=0到N-1，最后得到的f[N-1][V]就是最后的答案。

? 上述算法的時間復雜度為O(VN)，空間復雜度也是O(VN)。時間復雜度是最優(yōu)的，而空間復雜度可以進一步優(yōu)化：我們注意到在公式f[i][j]=max{f[i-1][j],f[i][j-C[i]]+W[i]}中，對于j從0到V，f[i][j]只與f[i-1][j]有關(guān)，而與i-2，i-3等情況下的f無關(guān)，所以我們只需要考慮前一次迭代(亦即i-1)的結(jié)果就可以。亦即f[j]=max{f[j],f[j-C[i]]+W[i]}.又因為在計算f[j]時用到了比j小的f：f[j-C[i]]，所以在對j進行迭代時應該從后向前迭代：?

?

      
        1
      
      
        for
      
      (
      
        int
      
       i=0;i<N;i++
      
        ){

      
      
        2
      
      
        for
      
      (
      
        int
      
       j=V;j>=0;j--
      
        ){

      
      
        3
      
      
        if
      
      (j-item[i][0]>=0){
      
        //
      
      
        此處判斷是為了防止將j物品放入容量小于C[j]的背包中
      
      
        4
      
                           f[j]=max(f[j],f[j-item[i][0]]+item[i][1
      
        ]);

      
      
        5
      
      
                        }

      
      
        6
      
      
                    }           

      
      
        7
      
               }
    

? 我們可以用一個例子來展示一下上述代碼迭代的過程。取V=10，N=3.三個物品的體積分別為3,4,5.價值分別為4,5,6，迭代過程中f數(shù)組的值為：

? 0 0 0 4 4 4 4 4 4 4 4
? 0 0 0 4 5 5 5 9 9 9 9
? 0 0 0 4 5 6 6 9 10 11 11

? 第一行為只考慮第1個物品的情況。所有容量大于等于3的背包的價值都為該物品的價值：4.

? 第二行為只考慮前2個物品的情況。所有容量大于等于7的背包可以同時容納前2個物品，價值為4+5=9，容量為4-6的背包可以容納第2個物品，價值為5，容量為3的背包可以容納第1個物品，價值為4.

? 第三行以此類推。

? 我們?nèi)∽詈?行的最后一個數(shù)字為結(jié)果，亦即考慮所有3個物品的體積為10的背包的最大價值，為11.

參考文獻：

? [1] 0/1問題 動態(tài)規(guī)劃法

? [2] 背包問題九講 第一講 0/1背包問題

? [3] 背包之0/1背包 完全背包 多重背包詳解

?

基本算法-0/1背包問題