单调队列优化多重背包

在多重背包模型上按重量余数分类,把每类转移化为长度至多 c_i+1 的滑动窗口最小值,用单调队列把 O(nmc) 降为 O(nm)。

时间 O(nm),空间 O(m) · 标签 动态规划 / 多重背包 / 单调队列 / DP 优化

问题形式

在 多重背包 模型中,固定第 𝑖 种物品,转移为

𝑓(𝑖,𝑗)=min0≤𝑘≤𝑐𝑖{𝑓(𝑖−1,𝑗−𝑘𝑤𝑖)+𝑘𝑣𝑖},

其中约定 𝑓(𝑖−1,𝑥)=+∞(𝑥<0)。直接枚举 𝑘 需要 𝑂(𝑛𝑚𝑐)。下面固定物品和重量余数,把每个转移化为滑动窗口最小值。

余数类

固定物品 𝑖 和余数 𝑟∈[0,𝑤𝑖),令

𝑗=𝑝𝑤𝑖+𝑟,𝑔𝑟(𝑖,𝑝)=𝑓(𝑖,𝑝𝑤𝑖+𝑟).

记 𝐾𝑝=min(𝑐𝑖,𝑝),并令 𝑗𝑘=(𝑝−𝑘)𝑤𝑖+𝑟。枚举 𝑘 后,剩余重量为 𝑗𝑘,所以

𝑔𝑟(𝑖,𝑝)=min0≤𝑘≤𝐾𝑝{𝑓(𝑖−1,𝑗𝑘)+𝑘𝑣𝑖}.

令 𝑡=𝑝−𝑘,则 𝑘=𝑝−𝑡,且

max(𝑝−𝑐𝑖,0)≤𝑡≤𝑝.

定义

ℎ𝑟(𝑖−1,𝑡)=𝑓(𝑖−1,𝑡𝑤𝑖+𝑟)−𝑡𝑣𝑖,

得到

𝑔𝑟(𝑖,𝑝)=𝑝𝑣𝑖+minmax(𝑝−𝑐𝑖,0)≤𝑡≤𝑝ℎ𝑟(𝑖−1,𝑡).

固定 𝑟 后,𝑝 递增时窗口 [max(𝑝−𝑐𝑖,0),𝑝] 只向右滑动,窗口长度至多为 𝑐𝑖+1。因此可以用单调队列维护 ℎ𝑟(𝑖−1,𝑡) 的最小值。

单调队列

对每个余数 𝑟 单独扫描 𝑝:

  • 把当前的 𝑡=𝑝 加入队尾,同时弹出队尾中 ℎ𝑟(𝑖−1,𝑡) 不小于它的下标。
  • 弹出所有 𝑡<max(𝑝−𝑐𝑖,0) 的队首。
  • 队首就是窗口最小值,代回 𝑔𝑟(𝑖,𝑝)=𝑝𝑣𝑖+ℎ𝑟(𝑖−1,𝑡)。

每个物品的所有余数类合计扫描 𝑂(𝑚) 个容量,因此单层转移为 𝑂(𝑚),总时间为 𝑂(𝑛𝑚)。

用两行滚动数组保存上一层和当前层的 𝑓,空间为 𝑂(𝑚)。

正确性

模型本身的正确性见 多重背包;这里验证余数类变换和单调队列没有改变转移。

固定 𝑖 和 𝑟 后,所有形如 𝑗=𝑝𝑤𝑖+𝑟 的容量被同一余数类覆盖,不同余数类互不重叠。枚举 𝑘 表示第 𝑖 种物品选了 𝑘 个,剩余重量 (𝑝−𝑘)𝑤𝑖+𝑟 对应 𝑓(𝑖−1,(𝑝−𝑘)𝑤𝑖+𝑟)。令 𝑡=𝑝−𝑘 后,𝑘=𝑝−𝑡,把 𝑝𝑣𝑖 从窗口中分离,窗口内的量正是 ℎ𝑟(𝑖−1,𝑡)。因此上面的等式与原转移逐项对应。

窗口端点随 𝑝 单调右移,单调队列始终保存窗口内未被支配的候选,队首就是最小值。代回后得到 𝑔𝑟(𝑖,𝑝),所以每层转移正确;再按物品维归纳即可。

易错点

  • 余数分类要求 𝑤𝑖>0;𝑤𝑖=0 先按模型页的边界处理。
  • 窗口长度至多为 𝑐𝑖+1,对应 𝑘=0,…,𝑐𝑖;删除队首的条件是 𝑡<𝑝−𝑐𝑖。
  • ℎ𝑟 必须使用上一层的 𝑓(𝑖−1,𝑗);在原地滚动时要先保留旧行。
  • 取最大值时把 min 换成 max,并相应改变单调队列的比较方向。
  • 不同余数类的窗口互不相干,不能共用一个队列。
  • 下标越界的位置要保持 +∞;否则会被当成合法转移。
源码位置