泛化物品：物品即函数 h(v)

三种基础形态各异：h 不必单调。多重物品的 h 在件数上限后封顶；01 物品的 h 是单峰；完全物品的 h 是等距阶梯。「选与不选」在 01 物品里对应 v ∈ {0, C} 两个有意义的取值。两峰之间的零位反映该费用恰好不能被等长包整除，余出的容量本身不增值。

NOTES · 三种基础物品的 h 函数对照

以 (C,W)=(3,5)、V=10 为例，三种基础形式的 h 函数（均采用「分配费用恰为 v 时所达到的最大价值」）：

01 物品 · 单峰

h = [0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0]
v =  0  1  2  3  4  5  6  7  8  9 10

仅 h(3)=5，其余皆 0。

完全物品 · 阶梯

h = [0, 0, 0, 5, 0, 0, 10, 0, 0, 15, 0]
v =  0  1  2  3  4  5   6  7  8   9 10

h(kC)=kW:v=3 选 1 件、v=6 选 2 件、v=9 选 3 件。

多重物品(M=2)· 截断阶梯

h = [0, 0, 0, 5, 0, 0, 10, 0, 0, 0, 0]
v =  0  1  2  3  4  5   6  7  8  9 10

阶梯在 kC > MC 处被截断；此例 h(9) 不再为 15，因 M=2 仅允许选 2 件。

真正的应用 · 不规则物品

某商品有 3 种售卖方式——单件 5 元换 8 分；双件套 9 元换 15 分（含折扣）；三件加赠 12 元换 20 分（含赠品）。三种方式互斥，且整体至多购买一次。

它不符合 01 / 完全 / 多重的标准形式（价格点不构成等比阶梯，整体只能选一次），但其泛化函数可直接写出：

h(0) = 0 · h(5) = 8 · h(9) = 15 · h(12) = 20 · 其他 v: h(v) = 0

把该 h 直接代入泛化背包框架求解即可，无须为每种售法单独建模或拆分。这正是泛化物品视角的核心价值——为不规则物品形式提供统一处理框架。可在上方 demo 切换到「自定义」，点击立柱将其绘制出来试验。

NOTES · 记号约定 · 泛化物品的函数语义

h(v) 表示泛化物品在费用 v 处的最大价值贡献，定义域 $v \in [0, V]$，数组实现即 $h[0..V]$。理解这种「形态多样性」是本讲关键——既有背包形式只是泛化物品的特例。

「泛化物品之和」$\oplus$ 是结合且交换的二元运算，因此 N 件物品的求和顺序不影响结果。这对工程实现至关重要：可按任意次序处理物品（包括并行 / 流式）。

▸ 观察：f 并非 h 与 g 的逐点相加——它是在「任意分配总费用」的所有方式中取最大。若 h、g 来自两件独立 01 物品 $(C_1,W_1)$ 与 $(C_2,W_2)$，则 f(V) 即为这两件构成的 01 背包子问题最优值。解读：f 的值域涵盖「仅选 h」「仅选 g」「两件都选」的全部分配方案。

NOTES · 统一框架的复杂度代价

求 N 件泛化物品之和：对每件做一次 max-卷积，单次 $O(V^2)$,N 件累计 $O(NV^2)$。

这较 01 / 完全 / 多重背包的 $O(NV)$ 慢一阶。差异源于：专用算法利用了 h 的结构（如 01 物品仅在两点非零）简化内层枚举，而泛化方法对任意 h 一视同仁。

实践中，物品有可识别结构时仍应用专用算法；泛化视角的价值在于统一抽象而非性能——它提供了讨论「任意物品形式」的共同语言。

NOTES · 关键概念出处 · (max,+)-卷积

$\oplus$ 运算在数学文献中称为 (max,+)-卷积（也称热带卷积），是热带几何与热带半环代数的核心运算。其复杂度下界仍是开放问题——通用 $O(V^2)$ 是否可改进到 $O(V^(2-\varepsilon ))$ 与 SETH（强指数时间假设）有等价关系(见 Cygan et al., On Problems Equivalent to (min,+)-Convolution, ICALP 2017)。在 ML 引擎（DP 解码）、对偶分解、网络流中，(max,+)-卷积频繁出现。

延伸 · 背包的代数化：把 max 替换为 min / sum / OR 等聚合算子，得到一族广义 DP 问题——这正是第 9 讲的主题。届时本讲的 $\oplus$ 被推广为聚合算子 ⊗，把背包族纳入更广义的 DP 范式。

通向第 9 讲 · 问法变化：第 9 讲系统讨论问法变化——同一状态空间下，只把聚合算子从 max 换成 min / sum / OR，即可在不动 DP 框架的前提下分别处理最少件数(min)、方案数(sum)、可行性判定(OR)等多种问法。本讲建立的「物品即函数」视角，正是这一替换的形式化基础：转移结构不变，变的只是函数之和所用的算子。

试一试：默认「平台主券档位」——h(v) 在 v=200, 500, 1000 三个触发阈值处阶跃，阶跃之间是平台，这是「门槛达到则锁定该档减免」的图形语言。切换到「A 店主券档位」是 2 级阶梯（¥40 / ¥70，阈值 300 / 500）；切换到「服饰品类券档位」也是 2 级（¥50 / ¥100，阈值 300 / 600）——同一形态、不同参数。

NOTES · 把多家平台 / 店铺的阶梯券组合起来 · ⊕ 的真实用途

单一阶梯券 h(v) 只是「一个泛化物品」——它的价值在于可被组合：用户同一笔订单常同时面对多个独立档位族（平台档 / 店铺档 / 品类档），跨族可叠加但族内互斥。把每族表示为一个 $h_i$，跨族叠加即是「泛化物品之和」一节的 max-卷积：

f(V) = ( h_platform ⊕ h_shopA ⊕ h_category )(V)

语义：在购物车总额 V 约束下，把额度任意分配给三族（每族选一档或不选），最大化总减免。复杂度 $O(NV^2)$（N = 档位族数）；对 V=1500, N=3，约 7×10⁶ 次内层加法，桌面端毫秒级完成。

与第 4 讲混合背包的关系：第 4 讲展示「按物品类型分发 transition」的工程模式；本讲是同一抽象的另一面——不同类型物品的 h 形状不同（01 单峰 / 完全等距阶梯 / 多重截断阶梯 / 本节非递减阶梯），但 $\oplus$ 求和过程形状无关。这是「接口同构 → 实现各异」的算法版。