1. 多重背包问题概述

多重背包问题是动态规划中的经典问题，它介于01背包和完全背包之间。给定n种物品，每种物品有重量w_i、价值v_i和数量k_i，背包容量为W，要求在不超过背包容量的前提下，选择物品使得总价值最大。

与01背包（每种物品只能选0或1次）和完全背包（每种物品可以选无限次）不同，多重背包中每种物品有明确的选取上限k_i。这使得问题更加复杂，但也更贴近实际应用场景。

2. 朴素多重背包解法分析

2.1 状态转移方程

定义f[i][j]表示考虑前i种物品，背包容量为j时的最大价值。状态转移方程为：

f[i][j] = max(f[i-1][j-k*w_i] + k*v_i) for k in 0..min(k_i, j/w_i)

这个方程的含义是：对于第i种物品，我们可以选择0到k_i个，但要确保总重量不超过j。

2.2 时间复杂度分析

朴素解法需要三重循环：

1. 外层循环n种物品
2. 中层循环背包容量W
3. 内层循环物品数量k_i

总时间复杂度为O(nWk_max)，当k_i较大时效率很低。例如当n=100，W=1e5，k_i=1e5时，复杂度达到1e12，完全不可接受。

3. 单调队列优化原理

3.1 状态转移的重构

观察状态转移方程，我们发现对于固定的i和j%w_i，j的变化是线性的。设y = j%w_i，x = j/w_i，可以重写方程为：

f[i][x*w_i + y] = max(f[i-1][(x-k)*w_i + y] + k*v_i) for k in 0..min(k_i, x)

令g[x][y] = f[i][xw_i + y]，g'[x][y] = f[i-1][xw_i + y]，则方程变为：

g[x][y] = max(g'[x-k][y] + k*v_i) for k in 0..min(k_i, x)

3.2 单调队列的应用

进一步变形，设G[x][y] = g'[x][y] - x*v_i，则方程变为：

g[x][y] = max(G[x-k][y]) + x*v_i for k in 0..min(k_i, x)

现在问题转化为：对于每个固定的y，我们需要在滑动窗口[x-k_i, x]内找到最大的G值。这正是单调队列的典型应用场景。

4. 单调队列优化实现细节

4.1 队列维护

对于每个y∈[0,w_i-1]，我们维护一个单调队列：

1. 队列中存储的是x坐标
2. 保持队列中G[x][y]单调递减
3. 确保队列中的x在有效窗口[x-k_i, x]内

4.2 算法步骤

1. 初始化f数组
2. 对于每个物品i： a. 对于每个余数y∈[0,w_i-1]： i. 初始化空队列 ii. 对于x从0到(W-y)/w_i： - 弹出队首超出窗口的元素 - 维护队列单调性 - 将当前x加入队列 - 计算f[i][xw_i + y] = G[q.front()][y] + xv_i

4.3 复杂度分析

优化后，每个物品的处理时间为O(W)，总复杂度降为O(nW)，与01背包相同。空间复杂度可以通过滚动数组优化到O(W)。

5. 代码实现与解析

#include <iostream> #include <deque> #include <array> using namespace std; constexpr int MAXV = 4e4 + 10; constexpr int MAXN = 1e2 + 10; int n, W; array<int, MAXN> v, w, k; array<array<int, MAXV>, 2> f; // 滚动数组 deque<int> q; int main() { cin >> n >> W; for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> k[i]; int last = 0, now = 1; for (int i = 1; i <= n; ++i) { for (int y = 0; y < w[i]; ++y) { q.clear(); for (int x = 0; x * w[i] + y <= W; ++x) { // 维护窗口大小 while (!q.empty() && q.front() < x - k[i]) q.pop_front(); // 维护单调性 while (!q.empty() && f[last][q.back()*w[i]+y] - q.back()*v[i] <= f[last][x*w[i]+y] - x*v[i]) q.pop_back(); q.push_back(x); f[now][x*w[i]+y] = f[last][q.front()*w[i]+y] - q.front()*v[i] + x*v[i]; } } swap(last, now); } cout << f[last][W] << endl; return 0; }

6. 应用实例分析

6.1 CF372C Watching Fireworks

题目大意：城镇有n个位置，m次烟花表演。每次烟花在a_i位置，时间为t_i，快乐值为b_i。你每秒最多移动d距离，求最大快乐值。

解法：

1. 定义f[i][j]表示第i次烟花时在位置j的最大快乐值
2. 转移方程：f[i][j] = max(f[i-1][k] - |a_i-j| + b_i)，其中|k-j|≤d*(t_i-t_{i-1})
3. 使用单调队列优化求滑动窗口最大值

6.2 洛谷P1886 滑动窗口

经典单调队列练习题，直接应用窗口最大值/最小值查询即可。

7. 常见问题与调试技巧

7.1 队列维护错误

常见错误包括：

1. 窗口大小计算错误：确保q.front()在有效范围内
2. 单调性维护错误：比较时注意是维护最大值还是最小值队列

调试方法：

1. 打印队列内容，检查是否保持单调
2. 验证窗口边界是否正确

7.2 边界条件处理

特别注意：

1. w[i]=0的情况需要特殊处理
2. 初始条件f[0][0]=0，其他为-∞
3. 滚动数组的切换要正确

7.3 性能优化

1. 使用原生数组代替STL容器可以提升速度
2. 对于稀疏物品（w_i很大），可以跳过无效的y循环
3. 使用快速输入输出（ios::sync_with_stdio(false)）

8. 扩展与变种

8.1 混合背包问题

同时存在01背包、完全背包和多重背包物品时：

1. 对每种类型采用对应的优化方法
2. 多重背包部分使用单调队列优化

8.2 分组背包的单调队列优化

当物品分组且每组只能选一个时，也可以应用类似的优化技巧。

8.3 二维费用背包

增加一维状态，单调队列需要相应扩展，复杂度变为O(nWU)。

在实际应用中，我发现单调队列优化虽然思想简单，但实现时容易出错。特别是在处理余数y和滚动数组时，需要格外小心。一个实用的调试技巧是先用小数据测试，打印中间结果验证单调性和窗口范围的正确性。