多重背包
每种物品有数量上限;在容量约束下选择件数,最小化总费用;给出 f(i,j) 转移、边界与变式。标签 动态规划 / 背包 / 多重背包 / 问题模型
模型
有 种物品,第 种物品重量为 、费用为 、数量上限为 ,背包容量为 。选择整数 ,满足
最小化总费用
这里 , 为非负整数,费用可正可负。最大化价值时把所有 换成 即可。
转移
记 为只考虑前 种物品、总重量恰为 时的最小费用。边界为
转移为
其中约定 ()。答案
若要求恰好装满容量 ,答案为 。若把状态解释为容量至多 ,可令 ,答案直接取 。
直接按转移枚举 的时间为 ;状态表为 ,滚动后为 。
正确性
对 归纳。 时只有 可行。设 对所有 已正确。固定 ,任一可行方案在最后一种物品上选 件,剩余部分是前 种物品、重量 的方案;反过来,任取 和对应的前 种方案,也能拼成可行方案。对所有 取最小得到 。答案再对所有不超过 的重量取最小。
边界
- 恰好装满与容量至多要分开:前者取 ,后者取 ,或改用至多状态的初始化。
- 时不能直接套用按重量枚举的转移:费用为负则取满 件,费用为正则不取;应作为预处理单独处理。
- 表示该物品不存在。
- 时数量上限在容量内不起作用,相当于该物品无上限。
- 最大化价值时把 换成 ,不可行初值改为 。
变式
- :0/1 背包。
- :完全背包。
- 多维容量:状态改为 ,转移对每个维度分别减去对应的重量。