【动态规划/背包问题】多重背包の单调队列优化
【动态规划/背包问题】多重背包の单调队列优化
前言
今天是我们讲解「动态规划专题」中的 「背包问题」的第十篇。
我们继续学习「多重背包の优化篇」。
今天我们将学习「多重背包」的另一种优化方式：单调队列优化。
第一种优化方式在：多重背包の二进制优化。
另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~
回顾
在最开始讲解 多重背包 时，我们就提到了「多重背包」的一维空间优化，无法优化时间复杂度。
将「多重背包」简单拆分成「01 背包」也同样无法减少状态数量，同时还会增加「扁平化」的运算成本。
这导致了朴素的「多重背包」解决方案复杂度是
的，只能解决数量级为
的问题。
在 上一节 中，我们结合「二进制思想」，将原本总数量为
的物品，等价拆分成了总数量为
的物品。
使得时间复杂度从
下降到了
，所能解决的问题数据范围也提升了一个数量级。
二进制优化的本质，是对「物品」做分类，使得总数量为
的物品能够用更小的
个数所组合表示出来。
而单调队列优化，某种程度上也是利用「分类」实现优化。只不过不再是针对「物品」做分类，而是针对「状态」做分类。
题目描述
有
种物品和一个容量为
的背包，每种物品「数量有限」。
第
件物品的体积是
，价值是
，数量为
。
问选择哪些物品，每件物品选择多少件，可使得总价值最大。
其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择「有限次数」的特点（在容量允许的情况下）。
示例 1：
输入: N = 2, C = 5, v = [1,2], w = [1,2], s = [2,1]
输出: 4
解释: 选两件物品 1，再选一件物品 2，可使价值最大。
单调队列优化
首先，我们还是使用一维空间优化的定义：
代表容量不超过
时的最大价值。
当遍历完所有的物品后，
就是最优解。
在朴素的多重背包解决方案中，当我们在处理某一个物品从
到
的状态时，每次都是通过遍历当前容量
能够装多少件该物品，然后从所有遍历结果中取最优。
但事实上，转移只会发生在「对当前物品体积取余相同」的状态之间。
举个 ?，假设当前我们处理到的物品体积和价值均为
，数量为
，而我们背包容量为
。
那么我们转移
到
时，其实存在如下规律：
只能由
、
、
转移而来
只能由
、
、
转移而来 ...
只能由
、
转移而来
只能由
、
转移而来
只能由
转移而来
只能由
转移而来
即某个状态
只能由
相同（
为当前物品体积，
为当前背包容量），并且比
小，数量不超过「物品个数」的状态值所更新。
因此这其实是一个「滑动窗口求最值」问题。
如果我们能够在转移
时，以
或者均摊
的复杂度从「能够参与转移的状态」中找到最大值，我们就能省掉「朴素多重背包」解决方案中最内层的“决策”循环，从而将整体复杂度降低到
。
具体的，我们定义一个
数组，用来记录上一次物品的转移结果；定义一个
数组来充当队列，队列中存放本次转移的结果。
由于我们希望在
复杂度内取得「能够参与转移的状态」中的最大值，自然期望能够在对队列头部或者尾部直接取得目标值来更新
。
我们发现如果希望始终从队头取值更新的话，需要维持「队列元素单调」和「特定的窗口大小」。
代码：
class Solution {
public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
int[] dp = new int[C + 1];
int[] g = new int[C + 1]; // 辅助队列，记录的是上一次的结果
int[] q = new int[C + 1]; // 主队列，记录的是本次的结果
// 枚举物品
for (int i = 0; i < N; i++) {
int vi = v[i];
int wi = w[i];
int si = s[i];
// 将上次算的结果存入辅助数组中
g = dp.clone();
// 枚举余数
for (int j = 0; j < vi; j++) {
// 初始化队列，head 和 tail 分别指向队列头部和尾部
int head = 0, tail = -1;
// 枚举同一余数情况下，有多少种方案。
// 例如余数为 1 的情况下有：1、vi + 1、2 * vi + 1、3 * vi + 1 ...
for (int k = j; k <= C; k+=vi) {
dp[k] = g[k];
// 将不在窗口范围内的值弹出
if (head <= tail && q[head] < k - si * vi) head++;
// 如果队列中存在元素，直接使用队头来更新
if (head <= tail) dp[k] = Math.max(dp[k], g[q[head]] + (k - q[head]) / vi * wi);
// 当前值比对尾值更优，队尾元素没有存在必要，队尾出队
while (head <= tail && g[q[tail]] - (q[tail] - j) / vi * wi <= g[k] - (k - j) / vi * wi) tail--;
// 将新下标入队
q[++tail] = k;
}
}
}
return dp[C];
}
}
- 时间复杂度：
- 空间复杂度：
总结
今天我们学习了「多重背包の单调队列优化」。
与对「物品」做拆分的「二进制优化」不同，「单调队列优化」是对「状态」做拆分操作。
利用某个状态必然是由余数相同的特定状态值转移而来进行优化。
单调队列优化是三种传统背包问题中最难的部分。
不过这里所谓的难，也主要是针对当年楼教主提出这个优化思路的那个年代而言。
这些年，这种根据“取余”对状态做划分，然后转换为「滑动窗口」问题，配合某种数据结构（单调队列/哈希表）来实现优化的方式，早就出现在各种题目中了。
例如 30. 串联所有单词的子串、1787. 使所有区间的异或结果为零 ...
背包问题（目录）
- 01背包 : 背包问题 第一讲
- 完全背包 : 背包问题 第四讲
- 多重背包 : 背包问题 第八讲
- 多重背包（优化篇）
- 【上】多重背包（优化篇）: 背包问题 第九讲
- 【下】多重背包（优化篇）: 本篇
- 混合背包
- 【练习】混合背包
- 分组背包
- 【练习】分组背包
- 多维背包
- 【练习】多维背包
- 树形背包
- 【练习篇】树形背包
- 背包求方案数
- 【练习】背包求方案数
- 背包求具体方案
- 【练习】背包求具体方案
- 泛化背包
- 【练习】泛化背包
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。