### 单调队列优化多重背包学习笔记#### 概述单调队列是一种用于优化滑动窗口和单调栈问题的数据结构。在多重背包问题中，我们可以利用单调队列来优化动态规划的时间复杂度，从而提高算法的效率。#### 问题背景多重背包问题是一种经典的背包问题，其特点是每个物
摘要：背景 考虑如下的背包问题： 给定 (n) 种物品和一个背包，第 (i) 种物品的体积为 (c_i)，价值为 (w_i)，并且有 (m_i) 个。背包的总容量为 (C) 。设计一种装物品的方法，使装入背包的物品总价值最
背景
考虑如下的背包问题：
给定 \(n\) 种物品和一个背包，第 \(i\) 种物品的体积为 \(c_i\)，价值为 \(w_i\)，并且有 \(m_i\) 个。背包的总容量为 \(C\) 。设计一种装物品的方法，使装入背包的物品总价值最大。
考虑朴素的做法。我们枚举每个物品，枚举背包容量，再枚举每种物品选了几件。使用滚动数组优化后，我们写出如下的转移方程：
\[dp_j = \max\{dp_{j-kc_i}+kw_i\},\ 1\le k\le \min\{m_i,\frac{j}{c_i}\}
\]
使用 \(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\)，带入原方程，我们有：
\[dp_{b+yc_i} = \max\{dp_{b+(y-k)c_i}+kw_i\},\ 1\le k\le \min\{m_i,\frac{j}{c_i}\}
\]
再令 \(x = y-k\)，我们有：
\[dp_{b+yc_i} = \max\{dp_{b+xc_i}-xw_i+yw_i\},\ y-\min\{m_i,\frac{j}{c_i}\}\le x\le y
\]
把 \(yw_i\) 提出来，然后我们就可以用单调队列维护 \(\max\{dp_{b+xc_i}-xw_i\}\)，从而把复杂度降低到 \(\mathcal O(nC)\)。
复杂度分析
外层 \(i\) 共循环 \(n\) 次；内层 \(b,y\) 加起来共循环 \(c\cdot \frac{(C-b)}{c} \approx C\) 次，且每个 \(y\) 只进出队列一次。总复杂度为 \(\mathcal O(nC)\)。复杂度分析建议搭配下文模板题代码食用以加深理解。
例题
Luogu P1176 宝物筛选
这是一道模板题。可以对照代码进一步理解上文的推导。
#include<iostream>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MIKU 0
using namespace std;
int n, C;
int q[100005], hd, tl;
int dp[100005], tmp[100005]; //用于维护 dp[b+y*c_i]-y*w_i
int main() {
fastio;
cin>>n>>C;
for(int i=1; i<=n; i++) {
int w, c, m; cin>>w>>c>>m;
if(m > C / c) m = C / c; //确定窗口长度，即每个物品最多取多少
for(int b=0; b<c; b++) { //按余数枚举
hd = tl = 0;
for(int y=0; y<=(C-b)/c; y++) { //j<=C，故 y<=j-b/c=(C-b)/c
tmp[y] = dp[b+y*c] - y*w; //单调队列维护这个值
while(hd < tl && tmp[q[tl-1]] <= tmp[y]) tl --; //单调递减，使队头最大
q[tl++] = y;
while(hd < tl && y - q[hd] > m) hd ++; //超出窗口丢掉
dp[b+y*c] = max(dp[b+y*c], tmp[q[hd]]+y*w); //dp决策，与转移方程是相同的
}
}
}
cout<<dp[C];
return MIKU;
}
Luogu P3423 [POI 2005] BAN-Bank Notes
这题考查的是方案记录。
题意
给定一些面值的硬币，共 \(n\) 种，每种硬币数量有限。求凑出 \(k\) 金额所需的最少硬币数，并输出一种方案。
思路
这题数据范围不大，但是下面还是提供一种单调队列优化的解法以巩固理解。
第一问就是一个裸的多重背包。我们把面值看作体积，价值恒为 \(1\) ，则问题转化成装满容量为 \(k\) 的背包得到的最小价值。
主要问题在于第二问。我们不妨定义 \(g_{i,j}\) 为考虑前 \(i\) 种硬币，恰好凑出 \(j\) 面额时，\(i\) 硬币选了多少枚。则当满足转移条件时，即 tmp[q[hd]]+y < dp[b+y*c] ，我们不仅进行状态的转移，还记录 \(g_{i,b+yc_i}=y-q_{hd}\) 。这里隐藏的原理是：进行状态转移时，所选的物品个数就是当前的窗口长度。如果你能自己想到这一点，说明你已经基本理解了单调队列优化多重背包的原理。
最后输出时，我们只需要从终状态按照 g[][] 逆推回每一步的决策，用一个栈来存储，最后输出栈内元素即可。
代码
#include<iostream>
#include<cstring>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MIKU 0
using namespace std;
int n, C;
int val[20005], cnt[20005];
int dp[20005], g[205][20005], tmp[20005];
int q[20005], hd, tl;
int stk[20005], top;
int main() {
fastio;
memset(dp, 0x3f, sizeof(dp)); dp[0] = 0;
cin>>n;
for(int i=1; i<=n; i++) cin>>val[i];
for(int i=1; i<=n; i++) cin>>cnt[i];
cin>>C;
for(int i=1; i<=n; i++) {
int c = val[i], m = cnt[i];
if(m > C/c) m = C / c;
for(int b=0; b<c; b++) {
hd = tl = 0;
for(int y=0; y<=(C-b)/c; y++) {
tmp[y] = dp[b+y*c] - y; //本来是 -y*w，但 w=1，省略。后文同。
while(hd < tl && tmp[q[tl-1]] >= tmp[y]) tl --;
q[tl++] = y;
while(hd < tl && y - q[hd] > m) hd ++;
if(tmp[q[hd]]+y < dp[b+y*c]) {
dp[b+y*c] = tmp[q[hd]] + y;
g[i][b+y*c] = y - q[hd];
}
}
}
}
cout<<dp[C]<<'\n';
for(int i=n, rst = C; i; i--) {
stk[++top] = g[i][rst];
rst -= g[i][rst] * val[i];
}
while(top) cout<<stk[top--]<<' ';
return MIKU;
}