01背包問題

背包問題

背包問題主要包含以下3種基本的問題：

• 01背包
• 完全背包
• 多重背包

其中對于每一種xx背包問題還存在一個特殊的情形，即要求背包恰好被裝滿，這種特殊問題的求解主要是在動态規劃的狀态數組的初始化做一下特殊的處理。

除此之外，有時候我們不僅僅要求背包能裝下的最大物品的價值，我們還希望得到具體的裝包方案，這裡就會涉及到狀态數組的回溯（Track），下面會舉例說明。

問題描述

01背包問題是背包問題中最簡單最基礎的一類問題，問題描述如下：

給定 n n 件物品，對于第ii件物品，其價值為 vi v i ，重量為 wi w i ，與此同時還存在一個體積為 V V 的背包，每件物品隻有一件，是以每件物品可以選擇是否放進背包，求背包能裝下的物品的最大價值PP。

對于該問題，對應的數學模型是一個簡單的01規劃問題：

對應的模型為：

s.t.  ∑ni=1 wi∗xi<=V,xi=0,1 s . t .     ∑ i = 1 n   w i ∗ x i <= V , x i = 0 , 1

maxP=∑ni=1vi∗xi m a x P = ∑ i = 1 n v i ∗ x i

解法

01背包問題常常采用動态規劃的方法去求解，狀态轉移方程為：

{fi,j=fi−1,jif wi>jfi,j=max(fi−1,j,fi−1,j−wi+vi) if wi<=j { f i , j = f i − 1 , j i f   w i > j f i , j = m a x ( f i − 1 , j , f i − 1 , j − w i + v i )   i f   w i <= j

fi,j f i , j 表示前 i i 種物品裝進容量為jj的背包裡面擷取的最大價值，是以對于第 i i 件物品來放進大小為jj的背包來講：

• 如果 wi>j w i > j ，那麼該物品放不進去，則此時的收益和前 i−1 i − 1 件物品放進大小為 j j 的背包的最大收益一樣，即fi,j=fi−1,jfi,j=fi−1,j；
• 若果 wi<=j w i <= j ， 則該物品可以放進去，但是此時是有兩種選擇的，即放進去或者不放進去，是以需要評估兩種選擇的收益大小：
  • 将第 i i 件物品不放進去：收益為fi−1,jfi−1,j
  • 将第 i i 件物品放進去，那麼此時前一個狀态隻可能是：前i−1i−1件物品放進大小為 j−wi j − w i 的背包中。是以将第 i i 件物品放入背包的收益是fi−1,j−wi+vifi−1,j−wi+vi
  • 最後兩個選擇中最大的便是目前的收益

代碼如下：

public static int knapsackProblemZeroOne(int[] value, int[] weight, int bagV) {
        int[][] dp = new int[value.length][bagV + ]; 
        // dp[i][j] 表示前i個物品，裝填大小為j的背包所能達到的最大價值;
        // 顯然因為value[0] = 0,dp[0][0~bagV] = 0 ;
        for (int i = ; i < value.length; i++) {
            for (int j = ; j <= bagV; j++) {
                if (weight[i] > j) {// 第i個物品放不進去
                    dp[i][j] = dp[i - ][j];
                } else {// 第i個物品能放進去
                    dp[i][j] = Math.max(dp[i - ][j], dp[i - ][j - weight[i]] + value[i]);
                }
            }
        }
        return dp[value.length - ][bagV];
    }
           

上述代碼裡面的兩層for循環，由于是從1開始的，是以對于對于參數

value

，裡面的有效資料應該也是從1開始計數的，是以在

value

數組和

weight

數組的第一個元素都應該置為0。

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] value = new int[] { , , , ,};// 物品的價值
        int[] weight = new int[] { , , , , };// 物品的重量
        int bagV = ;// 背包的大小
        System.out.println(knapsackProblemZeroOne(value, weight, bagV));
    }
           

實作細節：

• value和weight數組的第一個元素應該都為0，以便後續處理可以從1開始計數；
• dp狀态數組的列下标也是從1開始計數的，是以申請空間的時候應該是dp[n][bagV+1];

dp數組的求解正如如下表格一樣，從左上到右下依次求解：

空間優化

上述算法的時間複雜度為 O(NV) O ( N V ) ，其中 N N 為物品的數量，VV為背包的體積。

但是通過上述的狀态轉移方程我們發現，其實 fi,j f i , j 的值僅僅和 fi−1,j f i − 1 , j ， fi−1,j−wi f i − 1 , j − w i 有關，也就是說第 i i 件物品隻和前一件物品有關（dp二維數組的第i行可以通過第i-1行推出來），是以我們可以将二維數組改寫為一維數組，俗稱滾動數組。

public static int knapsackProblemZeroOneOptimization(int[] value, int[] weight, int bagV) {

        int[] dp = new int[bagV + ]; // dp[i][j] 表示前i個物品，裝填大小為j的背包所能達到的最大價值
        // 顯然，dp[0][0~bagV] = 0, dp[0~v.length-1][0] = 0;
        for (int i = ; i < value.length; i++) {
            for (int j = bagV; j >= weight[i]; j--) {//從後往前更新，因為後一項狀态dp[j]需要利用上一輪的j前面的狀态;
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        return dp[bagV];
    }
           

關鍵要了解這裡的寫法：

for (int j = bagV; j >= weight[i]; j--)
           

經過此番優化後，時間複雜度不變，空間複雜度降為O(V)O(V)。

狀态回溯

以上的算法隻是給出能夠得到的最大收益值 P P <script type="math/tex" id="MathJax-Element-68">P</script>，但是有時候我們希望得到具體的裝包方案，即我們需要知道哪些物品需要裝包，哪些不需要。

根據狀态數組從後往前倒退，即可得到一條路徑，将該路徑上的資訊儲存便可以得到方案。

對于dp[i][j]，該值來源于兩個地方:

• dp[i-1][j]
• dp[i-1][j-wi]

是以可以寫出下面的代碼求得裝包方案：

public static int[] tracback(int[][] dp, int[] weight, int bagV) {
        int[] res = new int[weight.length];
        int j = bagV;
        for (int i = weight.length - ; i >= ; i--) {//從後往前推
            if (dp[i][j] == dp[i - ][j]) {//dp[i][j]來源于dp[i-1][j]說明第i件物品裝不進去
                res[i] = ;
            } else {
                res[i] = ;
                j -= weight[i];
            }
        }
        res[] = dp[][j] >  ?  : ;
        return res;
    }
           

狀态回溯的求解正如如下二維表格一樣，從右下往左上倒推：

references

1. http://dongxicheng.org/structure/knapsack-problems/
2. https://blog.csdn.net/fx677588/article/details/68951593
3. https://baike.baidu.com/item/0-1%E8%A7%84%E5%88%92/5790449?fr=aladdin