多重背包问题的单调队列优化解析-北京尧图网络

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和滚动数组时需要格外小心。一个实用的调试技巧是先用小数据测试打印中间结果验证单调性和窗口范围的正确性。

多重背包问题的单调队列优化解析

相关推荐

HTML基础与核心元素解析：构建网页的基石

realloc 失败时原指针仍然有效：`p = realloc(p, n)` 这一行漏掉了一个临时变量

Java三国杀源码解析：从环境搭建到技能扩展的实战指南

更多资讯

超级具身智能“感知-决策中枢”研究（12）：基于FRA架构的语义总线与动态适配层

4.10 Canvas 组件实现自由绘图

大模型推理优化全解：KV Cache、PagedAttention、连续批处理与投机解码

让员工的浏览器“只干该干的事“：企业浏览器管控四道防线

Agentic AI 框架选型指南：OpenAI Agents SDK 与主流框架对比

Windows 64位 ImageJ 安装包选型：Java 与插件配置全攻略

今日更新

AI智能体开发实战：从技术原理到商业落地

OpenShell 完全定制指南：从安装到深度配置，打造高效 Windows 开始菜单

Superpowers技能体系全解析：从Skills引入到安装的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？