初識背包問題之「 0-1 背包」

2019 年 10 月 6 日
筆記

作者 | P.yh

來源 | 五分鐘學演算法

前言

背包問題可以說是一個老生常談的問題，通常被用作面試題來考查面試者對動歸的理解，我們經常說學演算法，初學者最難理解的就是「二歸」，一個叫遞歸，另一個叫動歸。

而背包問題屬於特殊的一類動歸問題，也就是按值動歸，這篇文章主要講解 0-1 背包 問題，如果讀者能看明白，那麼弄懂後續的 完全背包 以及 多重背包 這兩個知識點問題也是不大的。

通常背包這一類題目，題目大概就是給你一個容量或者大小固定的背包，然後要求你去用這個背包去裝物品，一般來說這些物品都是大小固定的，但是題目對物品的限定不同，衍生出來多種背包問題。

0-1 背包 問題中，物品個數有且僅有一個；
完全背包 問題中的物品個數是無限的；
多重背包 問題中的針對不同的物品，個數不一樣。

通常題目會要你求出背包能裝的最大價值（每個物品都會有容量和價值），當然也會有不一樣的問法，類似背包能否被裝滿，還有背包能裝的最大容量是多少，多少種方式填滿背包。

但是這些並不是背包問題的所有，還有 分組背包 問題，依賴背包 問題等等，因為考慮到這篇文章主要是針對面試，而不是競賽，這些有機會再去介紹。

0-1 背包

題目描述

有 N 件物品和一個容量為 V 的背包。放入第 i 件物品耗費的費用是 C[i] ,得到的價值是 W[i] 。求解將哪些物品裝入背包可使價值總和最大。求出最大總價值。

題目分析

對於每一個物品可以考慮放，或者不放；如果當前是第 i 個物品，當前背包裡面物品總價值是 Wcurrent，背包當前容量是 Vcurrent ，如果取這個物品，背包總價值會變成 Wcurrent + W[i] ，背包容量會變成 Vcurrent – C[i] 。

之前我們提到過，背包是屬於按值動歸，我們把背包劃分為 1-V個區間，也就是背包所有可能的大小，然後針對所有的物品，看看每個背包容量下能存放的最大價值，程式碼如下：

public static int zeroOnePack(int V, int[] C, int[] W) {      // 防止無效輸入      if ((V <= 0) || (C.length != W.length)) {          return 0;      }        int n = C.length;        // dp[i][j]: 對於下標為 0～i 的物品，背包容量為 j 時的最大價值      int[][] dp = new int[n + 1][V + 1];        // 背包空的情況下，價值為 0      dp[0][0] = 0;        for (int i = 1; i <= n; ++i) {          for (int j = 1; j <= V; ++j) {              // 不選物品 i 的話，當前價值就是取到前一個物品的最大價值，也就是 dp[i - 1][j]              dp[i][j] = dp[i - 1][j];                // 如果選擇物品 i 使得當前價值相對不選更大，那就選取 i，更新當前最大價值              if ((j >= C[i - 1]) && (dp[i][j] < dp[i - 1][j - C[i - 1]] + W[i - 1])) {                  dp[i][j] = dp[i - 1][j - C[i - 1]] + W[i - 1];              }          }      }        // 返回，對於所有物品（0～N），背包容量為 V 時的最大價值      return dp[n][V];  }

程式碼優化

空間優化：

僅僅看程式碼就可以發現，其實 dp 數組當前行的計算只用到了前一行，我們可以利用滾動數組來優化，但是再仔細看下去的話，你就會發現其實還可以更優，當前行的遍歷用到的值是上一行的前面列的值，如果我們第二層 for 循環遍歷的時候倒著遍歷的話，保證了前面更新的值不會被新計算的值覆蓋掉，我們僅僅用一維數組就可以完美解決問題，程式碼如下：

public static int zeroOnePackOpt(int V, int[] C, int[] W) {      // 防止無效輸入      if ((V <= 0) || (C.length != W.length)) {          return 0;      }        int n = C.length;        int[] dp = new int[V + 1];        // 背包空的情況下，價值為 0      dp[0] = 0;        for (int i = 0; i < n; ++i) {          for (int j = V; j >= C[i]; --j) {              dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);          }      }        return dp[V];  }

極端情況優化：

當背包的 V 特別大的時候，對於每一個物品都去遍歷一遍沒有意義，通過閾值來進行優化，優化的同時可以考慮將數組從大到小排個序：

public static int zeroOnePackOpt(int V, int[] C, int[] W) {      // 防止無效輸入      if ((V <= 0) || (C.length != W.length)) {          return 0;      }        int n = C.length;        int[] dp = new int[V + 1];        int bound, sum = 0, total = 0;      for (int i : C) {          total += i;      }        for (int i = 0; i < n; ++i) {          bound = Math.max(V - total + sum, C[i]);          sum += C[i];          for (int j = V; j >= bound; --j) {              dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);          }      }        return dp[V];  }

總結

0-1 背包 基本概況就是這些，當然可能問題的問法會不一樣，例如：

背包能不能被裝滿解題思路就是將 int 數組換成 boolean 數組，也不用去考慮物品的價值來，直接看容量夠不夠，能不能裝進背包即可
背包能裝的最大容量也很簡單，解法和上面「背包能不能被裝滿」一樣，只不過最後需要從後往前遍歷 dp 數組，直到找到 true
少種方式塞滿背包同樣是不用考慮物品的價值，用 int 數組，但是裡面記錄的是個數，背包被填充的個數，也就是把這裡的個數當作價值來看待，只不過 W[i] = 1。