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

前言

在前面的三篇文章當中，我們已經仔細的討論了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、計算機系統基礎、演算法與資料結構）知識，

標籤：其他

上一篇：博客從 CloudBase 遷移至云主機

下一篇：深入剖析斐波拉契數列