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 时间复杂度分析朴素解法需要三重循环外层循环n种物品中层循环背包容量W内层循环物品数量k_i总时间复杂度为O(nWk_max)当k_i较大时效率很低。例如当n100W1e5k_i1e5时复杂度达到1e12完全不可接受。3. 单调队列优化原理3.1 状态转移的重构观察状态转移方程我们发现对于固定的i和j%w_ij的变化是线性的。设y j%w_ix 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]我们维护一个单调队列队列中存储的是x坐标保持队列中G[x][y]单调递减确保队列中的x在有效窗口[x-k_i, x]内4.2 算法步骤初始化f数组对于每个物品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_i4.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; arrayint, MAXN v, w, k; arrayarrayint, MAXV, 2 f; // 滚动数组 dequeint 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距离求最大快乐值。解法定义f[i][j]表示第i次烟花时在位置j的最大快乐值转移方程f[i][j] max(f[i-1][k] - |a_i-j| b_i)其中|k-j|≤d*(t_i-t_{i-1})使用单调队列优化求滑动窗口最大值6.2 洛谷P1886 滑动窗口经典单调队列练习题直接应用窗口最大值/最小值查询即可。7. 常见问题与调试技巧7.1 队列维护错误常见错误包括窗口大小计算错误确保q.front()在有效范围内单调性维护错误比较时注意是维护最大值还是最小值队列调试方法打印队列内容检查是否保持单调验证窗口边界是否正确7.2 边界条件处理特别注意w[i]0的情况需要特殊处理初始条件f[0][0]0其他为-∞滚动数组的切换要正确7.3 性能优化使用原生数组代替STL容器可以提升速度对于稀疏物品w_i很大可以跳过无效的y循环使用快速输入输出ios::sync_with_stdio(false)8. 扩展与变种8.1 混合背包问题同时存在01背包、完全背包和多重背包物品时对每种类型采用对应的优化方法多重背包部分使用单调队列优化8.2 分组背包的单调队列优化当物品分组且每组只能选一个时也可以应用类似的优化技巧。8.3 二维费用背包增加一维状态单调队列需要相应扩展复杂度变为O(nWU)。在实际应用中我发现单调队列优化虽然思想简单但实现时容易出错。特别是在处理余数y和滚动数组时需要格外小心。一个实用的调试技巧是先用小数据测试打印中间结果验证单调性和窗口范围的正确性。