【动态规划/背包问题】多重背包の二进制优化
【动态规划/背包问题】多重背包の二进制优化
前言
今天是我们讲解「动态规划专题」中的 「背包问题」的第九篇。
今天我们将学习多重背包的第一种优化方式：二进制优化。
另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~
回顾
在 上一讲 中我们说到，多重背包问题无法像完全背包那样，通过一维空间优化来降低时间复杂度。
同时，对多重背包中的物品进行「扁平化」，可以彻底转换成 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 可以表达的范围是 0~13，而 1、2、4、8 可以表达的范围是 0~15，而我们要求的是表达 10，大于 10 的范围是不能被选择的。
所以我们可以在 1、2、4 （表达的范围是 0~7）的基础上，增加一个数 3（由 10 - 7 而来），这样就能满足我们需要表达的范围 0~10。
来看看通过「扁平化」来解决多重背包问题的代码：
class Solution {
public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
// 扁平化
List<Integer> worth = new ArrayList<>();
List<Integer> 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];
}
}
- 时间复杂度：
- 空间复杂度：
总结
今天我们学习了「多重背包」的二进制优化。
与「直接将第
物品拆分为
件」的普通扁平化不同，二进制优化可以「将原本数量为
的物品拆分成
件」，使得我们转化为 01 背包后的物品数量下降了一个数量级。
经过「二进制优化」的多重背包单秒能解决的数据范围从
上升到
。
但其还不是「多重背包」问题优化的上限，下一讲我们将会介绍比「二进制优化」更优的优化方式。
背包问题（目录）
- 01背包 : 背包问题 第一讲
- 完全背包 : 背包问题 第四讲
- 多重背包 : 背包问题 第八讲
- 多重背包（优化篇）
- 【上】多重背包（优化篇）: 本篇
- 【下】多重背包（优化篇）
- 混合背包
- 【练习】混合背包
- 分组背包
- 【练习】分组背包
- 多维背包
- 【练习】多维背包
- 树形背包
- 【练习篇】树形背包
- 背包求方案数
- 【练习】背包求方案数
- 背包求具体方案
- 【练习】背包求具体方案
- 泛化背包
- 【练习】泛化背包
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。