题意

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $s_i$ 件，每件体积为 $v_i$，价值为 $w_i$。求最大总价值。$N \le 10^3$，$V \le 5\times 10^4$，$s_i \le 10^4$。

思路

一句话本质：按体积取模分组后，每组内转移在等差数列下标上进行，形成滑动窗口最大值问题，用单调队列做到 $O(1)$ 转移。

二进制分组够快吗？

不够。每种物品拆出约 $14$ 个包，总物品数约 $1.4\times 10^4$，跑 01 背包是 $O(1.4\times 10^4 \cdot V) \approx 7\times 10^8$，远大于题目限制。需要 $O(NV)$ 级别的做法。

直接看转移方程，dependence 是什么样的？

对于第 $i$ 种物品（体积 $v$，价值 $w$，数量 $s$），$dp[c]$ 的候选前驱是 $dp[c-v],dp[c-2v],\dots,dp[c-s\cdot v]$。即它只依赖与 $c$ 相差 $v$ 的倍数的状态。

这个依赖结构提示什么？

把 $0\sim V$ 的容量按除以 $v$ 的余数分成 $v$ 组。第 $r$ 组包含位置 $r,r+v,r+2v,\dots$。不同余数的组之间完全独立——$dp[r+kv]$ 的转移只用到同组的前驱 $dp[r+(k-s)v],\dots,dp[r+(k-1)v]$。

分完组后，转移变成什么形式？

令组内下标为 $k$（位置 $r+kv$），只考虑前一轮 dp 值（记为 $g$，防止同一轮内重复读取）。则：

把 $(k-j)w$ 展开：$= \max_{k-s \le j \le k} \big(g[r+jv] - jw\big) + kw$。

这个式子像什么？

对于 $(g[r+jv]-jw)$ 这一项，窗口 $[k-s,k]$ 随 $k$ 增大而向右滑动——这是经典的滑动窗口最大值。窗口大小为 $s+1$，每步 $k$ 前进 1，新元素 $g[r+kv]-kw$ 入队，旧的 $k-s-1$ 出队。

怎么 $O(1)$ 取窗口最大值？

单调队列维护递减的 $g[r+jv]-jw$ 值。队首始终是窗口内最大值对应的下标 $j$。每步先弹出越界的 $j < k-s$，再弹出队尾不够优的元素，最后用队首计算 $dp[r+kv] = g[r+q_{\text{head}}\cdot v] + (k-q_{\text{head}})w$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * 多重背包问题 III — 单调队列优化
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 50005;
int n, V;
int dp[maxn], g[maxn];
int q[maxn], head, tail;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, dp, sizeof(dp));
        for (int r = 0; r < v; ++r) {
            head = 0, tail = 0;
            for (int k = 0; r + k * v <= V; ++k) {
                int idx = r + k * v;
                int val = g[idx] - k * w;
                while (head < tail && q[head] < k - s) ++head;
                while (head < tail && g[r + q[tail - 1] * v] - q[tail - 1] * w <= val) --tail;
                q[tail++] = k;
                dp[idx] = g[r + q[head] * v] + (k - q[head]) * w;
            }
        }
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

• 时间：$O(NV)$。每组余数内每个位置入队出队各一次，每件物品均摊线性于 $V$。
• 空间：$O(V)$（dp 数组 + 备份数组 g + 单调队列）。

总结

多重背包从 $O(NV\sum s_i)$ 到 $O(NV\log s_i)$ 再到 $O(NV)$，三个版本层层递进。单调队列优化的关键洞察是：固定 $v$ 后转移在等差数列下标上进行，第 $k$ 个位置只依赖前 $s$ 个位置中"最值"的那个，转化为滑动窗口即水到渠成。