深入剖析多重揹包問題（下篇）

前言

在前面的三篇文章當中，我們已經仔細的討論了01揹包問題和完全揹包問題以及多重揹包上篇，在本篇文章當中主要給大家介紹多重揹包問題的一種優化方法——二進位制優化多重揹包，如果你還沒有看過多重揹包上篇，你需要先閱讀多重揹包上篇。

多重揹包問題介紹

有 \(N\) 種物品和一個容量是 \(V\) 的揹包。第 \(i\) 種物品最多有 \(s_i\) 件，每件體積是 \(v_i\)，價值是 \(w_i\)。求解將哪些物品裝入揹包，可使物品體積總和不超過揹包容量，且價值總和最大。

注意：上面使用到的字元含義在本篇文章當中都一樣。

多重揹包問題跟01揹包和完全揹包的區別都是在物品的可用次數上，01揹包只能使用一次，多重揹包可用使用無數次，而多重揹包可用使用多次。

多重揹包的二進位制優化

二進位制優化的實現

在正式分析多重揹包的二進位制優化之前，我們先分析一下多重揹包的時間複雜度，假設我們有\(N\)件物品，平均每個物品的個數為\(S\)，那麼多重揹包的的時間複雜度為\(O(NSV)\)。而多重揹包的二進位制優化可以將這個時間複雜度降低到\(O(NVlog(S))\)。

在多重揹包上篇上篇當中我們提到了多重揹包的動態轉移方程（ \(T = min(S, \frac{V}{v_i})\)，其中\(S\)表示物品能夠選擇的次數，\(v_i\)表示物品的體積，\(V\)表示當前揹包的容量）：

從上面的公式我們可以知道，對於某個有\(S\)件的物品當中，我們要選擇一個合適的數位使得我們的收益最大，這個數位可能是\(1, 2, 3, 4, ..., S\)。我們在文章多重揹包上篇提到我們可以將多重揹包轉化成01揹包，我們將\(S\)個物品在邏輯上分成體積和價值相同的\(S\)個不同的物品，被分成\(S\)個不同的物品在進行動態選擇的時候與\(S\)個相同的物品是一樣的。比如說對於\(S\)個相同的物品\(A\)，我們在選擇3個的時候收益可以達到最大，那麼對於轉化之後的01揹包問題來說就選擇3個與\(A\)體積和價值相同的物品即可。

根據上面分析我們可以知道多重揹包能夠轉化成01揹包的原因就是多重揹包在轉化為01揹包之後，01揹包能夠有多重揹包選1個，選2個，選3個，...，選\(S\)個的效果。

而我們的二進位制優化也主要集中在這個地方。多重揹包的二進位制優化也是將多重揹包問題轉化成01揹包問題，但是不是將\(S\)個相同的物品轉化成\(S\)個體積和價值相同的不同的物品。根據上文的分析我們知道，我們在將多重揹包轉化成01揹包之後是需要保證01揹包能夠實現多重揹包選1個，選2個，選3個，...，選\(S\)個的效果。那麼我們如何實現這一點呢？下面程式碼主要顯示二進位制優化將多重揹包轉化成01揹包該往裝物品的價值和體積的集合里加入什麼東西。

Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
ArrayList<Integer> v = new ArrayList<>();
ArrayList<Integer> w = new ArrayList<>();
for (int i = 0; i < N; i++) {
    // 這個表示第 i 個物品的體積
    int vi = scanner.nextInt();
    // 這個表示第 i 個物品的價值
    int wi = scanner.nextInt();
    // 這個表示第 i 個物品有多少個
    int si = scanner.nextInt();
    // 這段程式碼主要是實現多重揹包能夠選擇1個
    // 選擇2個，...，選擇S個的效果
    for (int j = 1; j <= si; j *= 2) {
        si -= j ;
        v.add(vi * j);
        w.add(wi * j);
    }
    if (si > 0) {
        v.add(vi * si);
        w.add(wi * si);
    }
}

我們舉一個例子來分析上面的程式碼，假設我們加入一個物品\(A\)，它的個數為9，價值和體積分別為5和3。那麼在集合\(v\)和集合\(w\)當中的資料分別為：

上面的例子將9個\(A\)分成了\(A_1\)，\(A_2\)，\(A_3\)，以及\(A_4\)，\(A_1\)到\(A_4\)的體積和價值分別相當於1個，2個，4個，2個的\(A\)的體積和價值。我們在上文當中提到了，我們在將多重揹包轉化成01揹包之後是需要保證01揹包能夠實現多重揹包選1個，選2個，選3個，...，選\(S\)個的效果，那麼上面的轉化是如何實現這個效果的呢？

• 一個\(A\)：相當於\(A_1\)。
• 兩個\(A\)：相當於\(A_2\)。
• 三個\(A\)：相當於\(A_1 + A_2\)，也就是在動態選擇的時候選擇了\(A_1\)和\(A_2\)兩個物品。
• 四個\(A\)：相當於\(A_3\)。
• 五個\(A\)：相當於\(A_1 + A_3\)，也就是在動態選擇的時候選擇了\(A_1\)和\(A_3\)兩個物品。
• 六個\(A\)：相當於\(A_2 + A_3\)，也就是在動態選擇的時候選擇了\(A_2\)和\(A_3\)兩個物品。
• 七個\(A\)：相當於\(A_1 + A_2 + A_3\)，也就是在動態選擇的時候選擇了\(A_1\)、\(A_2\)和\(A_3\)三個物品。
• 八個\(A\)：相當於\(A_2 + A_3 + A_4\)，也就是在動態選擇的時候選擇了\(A_2\)、\(A_3\)和\(A_4\)三個物品。
• 九個\(A\)：相當於\(A_1 + A_2 + A_3 + A_4\)，也就是在動態選擇的時候選擇了\(A_1\)、\(A_2\)、\(A_3\)和\(A_4\)四個物品。

相信經過上面的例子之後你已經大致明白了二進位制優化的大致實現過程，二進位制優化也是將多重揹包轉化成01揹包但是和之前的轉化不同的是，我們不是將\(S\)個物品\(A\)劃分成\(S\)個體積和價值相同的物品，而是將其劃分成體積和價值是原來的物品1倍、2倍、3倍，....，\(2^n\)倍的物品，即\(1 + 2 + 4 + ... + 2^n + a = S\)，其中\(a\)是最後的剩下的餘數（\(a \lt 2^{n + 1}\)），比如上面最後一個2就是a = 9 - 1 - 2 - 4。這樣的劃分我們可以知道，我們劃分之後的物品的數目會少非常多。如果物品的次數的最大值是int型別的最大值，如果我們一個一個的劃分最多可以劃分超過20億個物品，而上面的劃分方式，我們劃分出來的物品不會超過32個，因此大大降低了時間複雜度。

之前一個一個的劃分我們的時間複雜度為\(O(NSV)\)，而像上面那樣劃分我們最大的時間複雜度為\(O(NVlog(S))\)，其中\(N\)表示物品的個數，\(S\)表示物品能夠選擇的平均次數，\(V\)表示揹包的容量。

上面就是我們使用二進位制優化方式將多重揹包轉化成01揹包的方式，完整程式碼如下（下方程式碼使用了單行陣列優化）：

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    ArrayList<Integer> v = new ArrayList<>();
    ArrayList<Integer> w = new ArrayList<>();
    for (int i = 0; i < N; i++) {
      int vi = scanner.nextInt();
      int wi = scanner.nextInt();
      int si = scanner.nextInt();
      for (int j = 1; j <= si; j *= 2) {
        si -= j ;
        v.add(vi * j);
        w.add(wi * j);
      }
      if (si > 0) {
        v.add(vi * si);
        w.add(wi * si);
      }
      System.out.println(v);
      System.out.println(w);
    }
    int[] f = new int[V + 1];
    for (int i = 0; i < v.size(); i++) {
      for (int j = V; j >= v.get(i); j--) {
        f[j] = Math.max(f[j], f[j - v.get(i)] + w.get(i));
      }
    }
    System.out.println(f[V]);
  }
}

二進位制優化的本質

我們知道任何一個數都有他的二進位制形式，任何一個數都可以由2的整數次冪相加得到：

假如我們有15個物品\(A\)，那麼我們會得到\(A_1\)，\(A_2\)，\(A_3\)，\(A_4\)，他們的價值和體積分別是\(A\)的1倍，2倍，4倍和8倍，這四個物品可以組成相當於任意整數倍的物品\(A\)的價值和重量，在這個問題當中就是1， 2， 4， 8可以組成1~15之間任意一個數。

因為我們最終可能\(S\)個物品當中全部選了，因此當我們將多重揹包轉化成01揹包之後，所有轉化之後的物品的價值和體積需要和\(S\)個物品相同，而\(S\)不一定恰好就是\(n\)個整數冪的值相加，因此在上文當中還提到了\(a\)，\(a\)就保證了我們最終可以取到1~\(S\)之間任意一個數。

總結

本篇文章主要給大家介紹的多重揹包問題的二進位制優化，裡面的邏輯還是稍微有點複雜的，可能需要大家仔細去體會，大家在看文字的時候可以參考程式碼仔細分析，可以理解的更好一點。

以上就是本篇文章的所有內容了，希望大家有所收穫，我是LeHung，我們下期再見！！！（記得點贊收藏哦！）

更多精彩內容合集可存取專案：https://github.com/Chang-LeHung/CSCore

關注公眾號：一無是處的研究僧，瞭解更多計算機（Java、Python、計算機系統基礎、演演算法與資料結構）知識。