多重背包

每种物品有数量上限;在容量约束下选择件数,最小化总费用;给出 f(i,j) 转移、边界与变式。

标签 动态规划 / 背包 / 多重背包 / 问题模型

模型

有 𝑛 种物品,第 𝑖 种物品重量为 𝑤𝑖、费用为 𝑣𝑖、数量上限为 𝑐𝑖,背包容量为 𝑚。选择整数 𝑘𝑖∈[0,𝑐𝑖],满足

∑𝑖=1𝑛𝑘𝑖𝑤𝑖≤𝑚,

最小化总费用

∑𝑖=1𝑛𝑘𝑖𝑣𝑖.

这里 𝑤𝑖>0,𝑐𝑖 为非负整数,费用可正可负。最大化价值时把所有 min 换成 max 即可。

转移

记 𝑓(𝑖,𝑗) 为只考虑前 𝑖 种物品、总重量恰为 𝑗 时的最小费用。边界为

𝑓(0,0)=0,𝑓(0,𝑗)=+∞(𝑗>0).

转移为

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

其中约定 𝑓(𝑖−1,𝑥)=+∞(𝑥<0)。答案

min0≤𝑗≤𝑚𝑓(𝑛,𝑗).

若要求恰好装满容量 𝑚,答案为 𝑓(𝑛,𝑚)。若把状态解释为容量至多 𝑗,可令 𝑓(0,𝑗)=0,答案直接取 𝑓(𝑛,𝑚)。

直接按转移枚举 𝑘 的时间为 𝑂(𝑛𝑚𝑐);状态表为 𝑂(𝑛𝑚),滚动后为 𝑂(𝑚)。

正确性

对 𝑖 归纳。𝑖=0 时只有 𝑓(0,0) 可行。设 𝑓(𝑖−1,𝑗) 对所有 𝑗 已正确。固定 𝑖,𝑗,任一可行方案在最后一种物品上选 𝑘 件,剩余部分是前 𝑖−1 种物品、重量 𝑗−𝑘𝑤𝑖 的方案;反过来,任取 𝑘 和对应的前 𝑖−1 种方案,也能拼成可行方案。对所有 𝑘 取最小得到 𝑓(𝑖,𝑗)。答案再对所有不超过 𝑚 的重量取最小。

边界

  • 恰好装满与容量至多要分开:前者取 𝑓(𝑛,𝑚),后者取 min0≤𝑗≤𝑚𝑓(𝑛,𝑗),或改用至多状态的初始化。
  • 𝑤𝑖=0 时不能直接套用按重量枚举的转移:费用为负则取满 𝑐𝑖 件,费用为正则不取;应作为预处理单独处理。
  • 𝑐𝑖=0 表示该物品不存在。
  • 𝑐𝑖≥⌊𝑚𝑤𝑖⌋ 时数量上限在容量内不起作用,相当于该物品无上限。
  • 最大化价值时把 min 换成 max,不可行初值改为 −∞。

变式

  • 𝑐𝑖=1:0/1 背包。
  • 𝑐𝑖≥⌊𝑚𝑤𝑖⌋:完全背包。
  • 多维容量:状态改为 𝑓(𝑖,𝑗1,…,𝑗𝑑),转移对每个维度分别减去对应的重量。
源码位置