泛化物品

1 从「物品是什么」问起

普通背包里，一件物品就是一对数 $(w,v)$：给它 $w$ 的空间，得到 $v$ 的价值，给别的空间什么都不给。

但如果把「物品」理解成一个函数呢？

用数组的说法：一个泛化物品就是一个数组 $h[0\dots C]$。

2 普通物品是特殊的泛化物品

• 01 物品 $(w,v)$：只有 $h(w)=v$，其余全是 $0$。
• 完全物品 $(w,v)$：当 $v$ 能被 $w$ 整除时 $h(v)=v'\cdot\frac{v}{w}$（即装几件拿几件的价值），其余为 $0$。
• 多重物品 $(w,v,m)$：同上，但限制件数不超过 $m$。
• 一个物品组：$h(v)$ 取组内所有费用恰为 $v$ 的物品的最大价值。

所以「泛化物品」不是新东西，只是把所有已有的背包对象统一成同一个形状。

3 泛化物品的和

真正有用的是运算。取两个泛化物品 $h$ 和 $l$，要用一定的费用从两者中取得最大价值，该怎么算？

对固定的费用 $v$，枚举分配给 $h$ 多少、给 $l$ 多少：

$f$ 自己也是一个定义在 $0\sim C$ 上的函数，也就是一个新的泛化物品，称为 $h$ 与 $l$ 的和。

这一步的复杂度是 $O(C^2)$。

理由是显然的：分配给这两件的总费用是固定的，怎么分配不影响可行性，所以只需取最优分配。

由此得到一个漂亮的结论：

求解一个背包问题，就是求它所有物品（泛化物品）之和；答案是这个和的 $0\sim C$ 上的最大值。

4 用它重新看前面几讲

这个视角能把已有算法解释得很统一：

注意合并的复杂度：用朴素方式求和是 $O(C^2)$。前面几讲之所以能做到 $O(C)$，是因为利用了物品的特殊结构——01 物品的 $h$ 只有 $h(w)=v$ 一个非零值，所以 $\max$ 里只有两项需要比较。这就是为什么 01 背包的转移是 $O(1)$ 而不是 $O(C)$。

5 一个具体的例子

考虑「每个物品可以取 $0,1,2$ 件，但第二件打折」这种奇怪规则。它显然不是 01/完全/多重中的任何一种。

用泛化物品描述：一件物品的 $h$ 是

它仍然是一个合法的泛化物品，所以仍然可以和别的物品「求和」。求和之后取最大值，就是答案。

只不过此时 $h$ 有 3 个非零位置，转移时要比 3 次而不是 2 次——这就是「物品越复杂，转移越慢」的由来。

6 小结

泛化物品是《背包问题九讲》里最抽象的一讲，但结论很朴素：

• 每件物品都是一个函数 $h(v)$；
• 「把两件物品放在一起」就是一次 $O(C^2)$ 的卷积式求和；
• 背包问题的答案，就是所有物品之和在 $0\sim C$ 上的最大值。

它的用途不在加速，而在建立一个统一的思考框架。遇到新变形时，先问「它的 $h$ 是什么、怎么求和」，比直接猜状态转移方程更可靠。

7 相关题解

暂无相关题解