标签:多重背包
2 个条目
-
概念 多重背包
每种物品有数量上限;在容量约束下选择件数,最小化总费用;给出 f(i,j) 转移、边界与变式。
2026-11-13 -
概念 单调队列优化多重背包
在多重背包模型上按重量余数分类,把每类转移化为长度至多 c_i+1 的滑动窗口最小值,用单调队列把 O(nmc) 降为 O(nm)。
2026-11-13
2 个条目
每种物品有数量上限;在容量约束下选择件数,最小化总费用;给出 f(i,j) 转移、边界与变式。
在多重背包模型上按重量余数分类,把每类转移化为长度至多 c_i+1 的滑动窗口最小值,用单调队列把 O(nmc) 降为 O(nm)。