离散资源分配
假设每个项目最多选一次,资源需求 是正整数,价值 非负,可用整数容量 。我们要选取总重量不超过 、总价值最大的项目集合。项目不能拆分时,按单位资源价值排序未必最优。
以下假设有限输入、整数重量及容量,并用精确运算。数学递推允许实数价值;下文位复杂度讨论则假设价值是以二进制编码的非负整数。
定义 3.2.1
(0–1 背包实例与容量表)
一个实例由 件物品及整数容量 组成,第 件的重量是整数 ,价值为 。若 ,则子集 称为可行。输出是可行 上 的最大值,以及一个取得此值的可行子集(证据)。
对 及整数 ,令
由于空集总是允许的,最大值是在有限非空的集合族上取的。实例的最优值为 。
状态记录哪些项目仍可用
下标 记录仍可使用哪些物品, 记录剩余多少容量。空集可行,故 。
定理 3.2.2
(容量递推)
对每个整数 ,有 ;对 ,
证明
(按是否选第 件划分可行子集)
固定 及 。 中重量不超过 的子集 恰属以下两类之一。若 ,则 且重量不超过 ,所以其价值至多为 。若 ,则 ,而 的重量不超过 ;因此 的价值至多为 。于是 不超过右边。
反过来,取得 的子集对 可行。当 时,把第 件加入取得 的子集,便得到 中重量不超过 、价值为 的子集。所以右边可以取得,等式成立。从基础行出发对 归纳,便证明了每个表项的递推,即使价值为零或有多个并列集合也一样。
证明透视
为什么上一行确保每件最多一次
选第 件后,剩余子问题是 ,不是 。上一行不可能再选第 件;若重用当前行,就允许重复,变成另一个无限件数模型。若只用一个数组,应从大到小更新容量,使 的值仍属上一阶段;从小到大则有同样重用风险。
这里使用的两种容量约定不可混淆。
常见错误
(混淆“至多”与“恰好”容量)
基础行对每个 都设 时, 是重量至多为 的最佳价值,而不是重量恰好为 的最佳价值。在下表中 ,但三件物品的任何子集(连空集在内)都没有恰好为一的重量。若要计算恰好重量的表,基础行须取 、对 取 ,递推不变;此时背包最优值是 ,而不是 。
表格与最优证据
例题 3.2.3
(三件物品的表格及其证据)
重量 、价值 、容量 时,容量 的各行为
在 ,不选第三件得七,选它得 ,所以不选。在 ,选第二件得 ,所以选它并回到 ,再选第一件。证据集合重量 、价值 。若两项相等,任选一分支均可重构最优解;价值为零时,更不能单凭表值推断集合唯一。
例题 3.2.4
(永远放不下或毫无贡献的物品)
在上一实例后加入第 4 件 及第 5 件 ,容量仍为 。由于对每个 都有 ,递推只出现第一种情况, 与 逐项相同。实例中最大的价值根本无法取得。
对第 5 件,当 时 。每一行对 都是非递减的,因为容量较大时可选的子集较多,所以 ,最优值仍是七。在 两个分支都给出零:不选第 5 件得 ,选它得 。在容量一时 与 都是最优证据;因此在称重构结果唯一之前,必须先固定平局规则。
例题 3.2.5
(从大到小的单数组扫描)
只保留一个数组 ,从 开始;对每件物品,按 的次序更新 。 的项不变,这正是递推的第一种情况。
- 第 1 件 :容量 读到的 都是 ,所以 。
- 第 2 件 : 得 ; 得 ; 得 。现在 。
- 第 3 件 : 得 ; 得 。现在 。
每处理完一件物品,数组都等于表中相应的一行。处理第 2 件、 时,扫描读到的 尚未被第 2 件改动,所以它仍属上一阶段。
反例模式
单位重量价值贪心可能失败
容量为四,有三个不同项目 。第一件的比例 大于较小项目的 ,按比例贪心先选它,剩余容量不足以再选一件,价值为五;两个较小项目合共重量四、价值六。它们是两个不同的 0–1 选择。
算法成本
命题 3.2.6
(填表计算的规模)
完整表可用 次算术运算及 个存储值填好。从大到小更新的单数组实现以 次运算及 个存储值求得 。
完整表有 项,每次更新用常数次算术运算及比较,这就证明了两个界。单数组实现只保留当前一行;重构集合则须保留适当选择或重算阶段。对二进制整数价值,表项不超过输入价值总和,因此位长度是输入长度的多项式;但一次算术运算不自动等于常数次位运算。
常见错误
(把 界称为多项式时间)
这个界以 的数值计算运算次数。输入只用约 个二进制位写出 ,所以容量 只占 位,表格却有 列。把 的位数加倍,可使填表方法的运行时间变为平方。因此这是伪多项式界:它是 与 的数值的多项式,而不是输入长度的多项式。
练习
快速检查
(重算 ,并说明所选项目。)
解答 · 答案
不选第三件得到 ,选它得到 ,故单选第三件。
快速检查
(只有重量二、价值三的一件物品时,为什么单数组从小到大更新会在容量四错得价值六?)
解答 · 答案
更新容量二为三后,从小到大扫描可在容量四读到该新值并再次加上同一物品,错得六。从大到小则读取上一阶段的零。
快速检查
(按正重量假设, 时最优值是多少?)
解答 · 答案
没有正重量物品可放入;空集价值零,故最优值为零。
快速检查
(两件不同物品的重量和价值都为一,而 。给出两个不同最优集合。)
解答 · 答案
两个单件集合均可行且价值为一;两件同选超过容量,因此两个单件集合都是最优。平局规则只需返回其中一个。