【动态规划/背包问题】多重背包の二进制优化（01背包问题动态规划算法 时间复杂度）

【动态规划/背包问题】多重背包の二进制优化（01背包问题动态规划算法 时间复杂度）

回顾

在 ​​上一讲​​ 中我们说到，多重背包问题无法像完全背包那样，通过一维空间优化来降低时间复杂度。

同时，对多重背包中的物品进行「扁平化」，可以彻底转换成 01 背包问题。

但由于处理的物品没有变少，因此枚举的情况也不会变少，时间复杂度也不会发生改变，反而增加了扁平化的成本，使得算法的常数变大。

我们目前学的多重背包在各维度数量级同阶的情况下，时间复杂度为 ，只能解决 数量级的问题。

题目描述

有 种物品和一个容量为 的背包，每种物品「数量有限」。

第 件物品的体积是 ，价值是 ，数量为 。

问选择哪些物品，每件物品选择多少件，可使得总价值最大。

其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择「有限次数」的特点（在容量允许的情况下）。

示例 1：

输入: N = 2, C = 5, v = [1,2], w = [1,2], s = [2,1] 输出: 4解释: 选两件物品 1，再选一件物品 2，可使价值最大。

二进制优化

二进制优化可以使得我们能解决的多重背包问题数量级从 上升为 。

所谓的「二进制优化」其实是指，我们如何将一个多重背包问题彻底转化为 0-1 背包问题，同时降低其复杂度。

在上一节我们的扁平化方式是直接展开，一个数量为 的物品等效于 。

这样并没有减少运算量，但是如果我们能将 变成小于 个数，那么这样的「扁平化」就是有意义的。

学过 Linux 的都知道文件权限最高是 7，代表拥有读、写、执行的权限，但其实这个 7 是对应了 1、2、4 三个数字的，也就是 ​​r:1​​​、​​w:2​​​、​​x:4​​ ，三种权限的组合共有 8 种可能性。

这里就采用了 3 个数来对应 8 种情况的“压缩”方法。

我们也可以借鉴这样的思路：将原本为 n 的物品用 ceil(log(n)) 个数来代替，从而降低算法复杂度。

7 可以用 ​​1、2、4​​​ 来代替，像刚刚提到的 10 ，我们可以使用 ​​1、2、4、3​​​ 来代替，你可能会有疑问，为什么是 ​​1、2、4、3​​​，而不是 ​​1、2、4、6​​​ 或者 ​​1、2、4、8​​ 呢？

其实把他们几个数加起来就知道了，​​1、2、4、6​​ 可以表达的范围是 013，而 ​​1、2、4、8​​ 可以表达的范围是 015，而我们要求的是表达 10，大于 10 的范围是不能被选择的。

所以我们可以在 ​​1、2、4​​ （表达的范围是 07）的基础上，增加一个数 3（由 10 - 7 而来），这样就能满足我们需要表达的范围 010。

来看看通过「扁平化」来解决多重背包问题的代码。

Java 代码：

class Solution { public int maxValue(int N, int C, int[] s, int[] v, int[] w) { // 扁平化 List worth = new ArrayList<>(); List volume = new ArrayList<>(); // 我们希望每件物品都进行扁平化，所以首先遍历所有的物品 for (int i = 0; i < N; i++) { // 获取每件物品的出现次数 int val = s[i]; // 进行扁平化：如果一件物品规定的使用次数为 7 次，我们将其扁平化为三件物品：1*重量&1*价值、2*重量&2*价值、4*重量&4*价值 // 三件物品都不选对应了我们使用该物品 0 次的情况、只选择第一件扁平物品对应使用该物品 1 次的情况、只选择第二件扁平物品对应使用该物品 2 次的情况，只选择第一件和第二件扁平物品对应了使用该物品 3 次的情况 ... for (int k = 1; k <= val; k *= 2) { val -= k; worth.add(w[i] * k); volume.add(v[i] * k); } if (val > 0) { worth.add(w[i] * val); volume.add(v[i] * val); } } // 0-1 背包问题解决方案 int[] dp = new int[C + 1]; for (int i = 0; i < worth.size(); i++) { for (int j = C; j >= volume.get(i); j--) { dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i)); } } return dp[C]; }}

Python 3 代码：

class Solution: def maxValue(self, N, C, s, v, w): # 扁平化 worth = [] volume = [] # 我们希望每件物品都进行扁平化，所以首先遍历所有的物品 for i in range(N): # 获取每件物品的出现次数 val = s[i] # 进行扁平化：如果一件物品规定的使用次数为 7 次，我们将其扁平化为三件物品：1*重量&1*价值、2*重量&2*价值、4*重量&4*价值 # 三件物品都不选对应了我们使用该物品0次的情况、只选择第一件扁平物品对应使用该物品1次的情况、只选择第二件扁平物品对应使用该物品2次的情况，只选择第一件和第二件扁平物品对应了使用该物品3次的情况... k = 1 while k <= val: val -= k worth.append(w[i] * k) volume.append(v[i] * k) k *= 2 if val > 0: worth.append(w[i] * val) volume.append(v[i] * val) # 0-1 背包问题解决方案 dp = [0] * (C + 1) for i in range(len(worth)): for j in range(C, volume[i] - 1, -1): dp[j] = max(dp[j], dp[j-volume[i]] + worth[i]) return dp[C]

总结

今天我们学习了「多重背包」的二进制优化。

与「直接将第 物品拆分为 件」的普通扁平化不同，二进制优化可以「将原本数量为 的物品拆分成 件」，使得我们转化为 01 背包后的物品数量下降了一个数量级。

经过「二进制优化」的多重背包单秒能解决的数据范围从 上升到 。

但其还不是「多重背包」问题优化的上限，下一讲我们将会介绍比「二进制优化」更优的优化方式。

最后

这是我们「刷穿 LeetCode」系列文章的第 ​​No.*​​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：​​github.com/SharingSour…​​

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。