单调队列优化多重背包 学习笔记 & 详解
背景考虑如下的背包问题：
给定 \(n\) 种物品和一个背包，第 \(i\) 种物品的体积为 \(c_i\)，价值为 \(w_i\)，并且有 \(m_i\) 个。背包的总容量为 \(C\) 。设计一种装物品的方法，使装入背包的物品总价值最大。
考虑朴素的做法。我们枚举每个物品，枚举背包容量，再枚举每种物品选了几件。使用滚动数组优化后，我们写出如下的转移方程：
\
使用 \(i,j,k\) 三层循环，复杂度为 \(\mathcal O(n^3)\) 。
一种有效的优化是二进制拆分优化。通过把 \(m_i\) 个物品拆分成 \(\log m_i\) 个物品组，每个物品组看成一个新物品，并使用 0/1 背包求解。但是，这并非最优的解法。
事实上。我们有 \(\mathcal O(nC)\) 的做法，即单调队列优化。
思路
首先我们知道，单调队列优化适用于涉及 \(i,j\) 的状态转移方程，且 \(j\) 被限制在一个与 \(i\) 有关的滑动窗口内，随着 \(i\) 的增长，不同的 \(i\) 对应的窗口范围有重叠。本题中，\(i,j\) 没有什么关系，不能优化。我们考虑优化 \(j,k\) 。此时，我们把 \(i\) 看作定值。
为了应用单调队列，我们需要找到 \(k\) 在 \(j\) 上的滑动窗口。我们发现，\(dp_{j}\) 只会由 \(dp_{j-kc_i},\ dp_{j-(k-1)c_i},\dp_{j-(k-2)c_i},\ \ldots\) 转移而来，\(dp_{j+c_i}\) 只会由 \(dp_{j},\ dp_{j-kc_i},\dp_{j-(k-1)c_i},\ \ldots\) 转移而来。这里，窗口发生了重叠。而这些依赖项又是 \(\bmod c_i\) 同余的。也就是说，为了产生滑动的窗口，我们不妨把外层枚举 \(j\) 改为枚举 \(j\bmod c_i\) 的余数 \(b\)，这样，对于每个 \(b\)，决策点 \(k\) 都被限制在了一个有重叠的滑动窗口中，且窗口长度为 \(\min\{m_i,\frac{j}{c_i}\}\)。 我们就可以使用单调队列优化。
下面，我们实现上面的思路。我们把有关 \(j,k\) 的状态转移方程改为有关 \(b\) 的形式。为此，我们定义如下变量：
令 \(j=b+yc_i\)，其中，\(b=j\bmod c_i\)，\(y=\lfloor\frac{j}{c_i} \rfloor\)，带入原方程，我们有：
\
再令 \(x = y-k\)，我们有：
\
把 \(yw_i\) 提出来，然后我们就可以用单调队列维护 \(\max\{dp_{b+xc_i}-xw_i\}\)，从而把复杂度降低到 \(\mathcalO(nC)\)。
复杂度分析
外层 \(i\) 共循环 \(n\) 次；内层 \(b,y\) 加起来共循环 \(c\cdot \frac{(C-b)}{c} \approx C\) 次，且每个 \(y\) 只进出队列一次。总复杂度为 \(\mathcal O(nC)\)。复杂度分析建议搭配下文模板题代码食用以加深理解。
例题
Luogu P1176 宝物筛选
这是一道模板题。可以对照代码进一步理解上文的推导。
#include#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);#define MIKU 0using namespace std;int n, C;int q, hd, tl;int dp, tmp;//用于维护 dp-y*w_iint main() { fastio; cin>>n>>C; for(int i=1; i>w>>c>>m; if(m > C / c) m = C / c;//确定窗口长度，即每个物品最多取多少 for(int b=0; bC; for(int i=1; i C/c) m = C / c; for(int b=0; b m) hd ++; if(tmp]+y < dp) { dp = tmp] + y; g = y - q; } } } } cout
页:
[1]