2026年3月20日
多重背包单调队列优化的完整数学推导
摘要： ​【多重背包单调队列优化的完整数学推导】在多重背包问题中，单调队列优化的核心思想是将所有背包容量状态 j∈[0,V] 按当前物品的体积 vᵢ 取余分组，使状态转移严格限制在同一 “同余类” 内，进而利用滑动窗口最大值的性质，通过单调队列高效维护最优决策。多重背包单调队列优化，如同将一条笔直的主干道， 阅读全文
posted @ 2026-03-20 19:07 Triwa 阅读(3) 评论(0) 推荐(0)
AcWing 6：多重背包问题 III ← 单调队列优化
摘要： ​【题目来源】https://www.acwing.com/problem/content/6/【题目描述】有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。【 阅读全文
posted @ 2026-03-20 15:58 Triwa 阅读(5) 评论(0) 推荐(0)