今天是我们讲解「动态规划专题」中的 「背包问题」的第十篇。
我们继续学习「多重背包の优化篇」。
今天我们将学习「多重背包」的另一种优化方式:单调队列优化。
第一种优化方式在:多重背包の二进制优化。
另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。
你也先可以尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 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. 使所有区间的异或结果为零 ...
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。