深入剖析多重背包问题（下篇）

技术分享 2年前 (2022-07-17) 0 999+

深入剖析多重背包问题（下篇）

前言

在前面的三篇文章当中，我们已经仔细的讨论了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)表示当前背包的容量）：

[dp[i][j] = max\ { \ dp[i - 1][j], \ dp[i - 1][j - v[i]] + w[i],\ dp[i - 1][j - v[i] * 2] + w[i] * 2, \ ..., \ dp[i - 1][j - v[i] * T] + w[i] * T\ } ]

从上面的公式我们可以知道，对于某个有(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)当中的数据分别为：

[v = [3, 6, 12, 6] ]

[w = [5, 10, 20, 10] ]

上面的例子将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]);   } }