关于算法:深入剖析多重背包问题下篇

深刻分析多重背包问题（下篇）

前言

在后面的三篇文章当中，咱们曾经认真的探讨了 01 背包问题和齐全背包问题以及多重背包上篇，在本篇文章当中次要给大家介绍 多重背包问题 的一种优化办法——二进制优化 多重背包 ，如果你还没有看过 多重背包上篇 ，你须要先浏览 多重背包上篇。

多重背包问题介绍

有 $N$ 种物品和一个容量是 $V$ 的背包。第 $i$ 种物品 最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

留神：下面应用到的字符含意在本篇文章当中都一样。

多重背包问题跟 01 背包 和齐全背包 的区别都是在物品的可用次数上，01 背包 只能应用一次，多重背包 可用应用无数次，而 多重背包 可用应用屡次。

多重背包的二进制优化

二进制优化的实现

在正式剖析 多重背包的二进制优化 之前，咱们先剖析一下 多重背包的工夫复杂度，假如咱们有 $N$ 件物品，均匀每个物品的个数为 $S$，那么多重背包的的工夫复杂度为 $O(NSV)$。而多重背包的二进制优化能够将这个工夫复杂度升高到 $O(NV)$。

在多重背包上篇上篇当中咱们提到了多重背包的动静转移方程（$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(32NV) = O(NV)$，其中 $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-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。