Ⅴ · 二维费用 · F[v][u]

二维费用：同时占两种资源

每件物品同时消耗两种费用——比如既占重量 $C_i$ 又占体积 $D_i$ ，背包对两者各有上限 V、U。决策仍然只有「选 / 不选」。做法非常直接：状态从 $F[v]$ 升一维成 $F[v][u]$ ，转移方程结构原封不动：

F[i][v][u] = max( F[i−1][v][u], F[i−1][v−Cᵢ][u−Dᵢ] + Wᵢ )

一维滚动后，两层费用都逆序遍历（理由与 01 背包（第 1 讲）的 v 逆序完全相同），就得到下面的二维表。答案在 $F[V][U]$ 。一维背包建立的全套技术——边界、空间压缩、循环方向——全部平移过来，这正是状态设计的可扩展性。

1 · 问题描述与二维状态

共 N 件物品，每件具有两种费用 $C_i$ 、 $D_i$ 与价值 $W_i$ ；两类容量上限分别为 V、U。设状态 $F[i][v][u]$ 表示「在物品 1..i 中选取、且总费用 1 不超过 v、总费用 2 不超过 u 时所能取得的最大价值」。对第 i 件仍只有「选 / 不选」两种决策。与 01 背包的差异仅在状态多了一维 u；结构、边界与空间压缩思路完全一致。下面把 i 维滚动压缩，展示二维表 $F[v][u]$ 随物品逐件加入的填充过程， $F[V][U]$ 即最终答案。

1.1 · 参考实现 · 滚动到一维 F[v][u]

把上面的状态机翻译成可运行的 JavaScript。关键:v 与 u 都必须双逆序循环，保证 $F[v-C][u-D]$ 在读取时仍是「未处理本件物品」时的值——与 01 背包一维实现中的逆序条件同源，只是从一维变成两维同时逆序。点 ▶ 运行 以默认参数 V=6、U=5、4 件物品执行一次。

记号约定 ·「前 i 件」的读法。状态 $F[i][v][u]$ 中的 i 是候选集合的上界，即允许从物品 {1..i} 中选取（每件至多一次）,v、u 分别为两类费用的上限。i 由 0 涨到 N 对应「逐步把每件物品纳入候选范围」——这是正向 DP 的视角。把「前 i 件」误读为「剩余未判定的 i 件」即对应逆向 DP（以 $G[j][v][u]$ 表示「从第 j 件到第 N 件中选取的最大价值」），两者算法上等价，本讲采用前者。

「最多取 K 件」是隐式二维费用。把「件数」视作第二维费用，每件物品的件数费用恒为 1、件数上限为 K，状态即 $F[v][u]$ （u 上限 = K）。但要分清：维度的本质是「被多种物品共同消耗、有全局上界的资源」。第 3 讲多重背包的 $M_i$ 是「每种物品自己一池、各有各的上限」，不跨物品共享 → 不是维度，硬加维会让状态膨胀成 $F[v, k_1, \dots , k_N]$ 爆炸，这正是第 3 讲走二进制拆分（把件数约束编码进物品结构本身）而非加维的原因。

约束形态	跨物品共享	全局上界	是维度？
「最多取 K 件」（全局）	✓ 共享同一池	✓ 统一为 K	是
多重背包的 $M_i$ （每种独立）	✗ 每种自己一池	✗ 各有各的上限	不是

速判口诀：约束写在「所有物品合计」上 → 维度；写在「每种物品自己」上 → 物品集变换。

复杂度：一维 $O(NV)$ → 二维 $O(NVU)$ → 三维 $O(NVUR)$ ，每加一维再乘该维上限。 $O(NVU)$ 仍属伪多项式（依赖 V、U 的数值大小而非编码长度），工程上通常要求 V、U ≤ 10³ 量级。

另一类典型形态 · 二维完全背包。如「营养规划」：每种食物有（热量、价格、营养评分）三元属性，约束为日卡路里 ≤ 2000、预算 ≤ 100 元，目标为营养评分总和最大。与物流装箱不同，每种食物可选取任意多份，故属二维完全背包——两维 v、u 均按顺序（正序）循环；与物流装箱（二维 01，双逆序）形成对照，展示「二维费用 × 物品类型」的组合空间。

2 · 应用案例 · 物流装箱

二维费用背包最经典的现实形态：每箱货物具有三元属性（重量、体积、利润），卡车具有载重与容积两类上限。点击任意货物可切换其「可装 / 损坏」状态，DP 即时重算。

2.1 · 参考实现 · 场景包装层

本演示在 Listing 1.1 的核心算法之上加一层场景包装:过滤损坏货物 → 委托给 knap2D。算法层不知道「损坏」概念，业务约束以两行解决——这是把抽象 DP 与具体业务规则解耦的标准做法。点 ▶ 运行以默认 8 件货物 / V=50 kg / U=20 m³（代码内 ×2 化为整数 40）执行一次。

关键概念出处。多维费用背包(multi-dimensional knapsack)在英文文献中亦称 multidimensional 0-1 knapsack problem。形式化与精确求解可见 Martello & Toth, Knapsack Problems(Wiley, 1990)第 9 章。三维及以上费用的工程方案、复整数域上的抽象视角与通向第 6 讲的衔接，详见文末延伸阅读。

3 · 应用案例 · 优惠券限张组合

「物流装箱」一节是「连续二维资源」（重量 + 体积）的经典场景，下面看一个「离散二维资源」的电商映射：同一笔订单上，用户同时受两个独立约束——购物车总额（V，支撑券门槛求和）与本单可用券名额（U，平台规定本单最多 U 张券，防套利）。每张券既消耗第一维（它的门槛）又消耗第二维（占用名额数，通常为 1，但部分联合券 / VIP 加成券占 2 张名额，让 $C_2$ 不再恒等于 1，形成非平凡 2D）。求最大总减免，即标准二维费用背包。

「加一维」是通用手段。再加约束就再加一维：限「最多拿 K 件」就开 $F[v][k]$ 、限「两个袋子分别装」就开 $F[v1][v2]$ ……代价是状态数（时间 / 空间）随维度相乘增长，所以能压维就压维。本讲的要点不是新算法，而是确认：状态设计可以正交地叠加约束。

4 · 延伸阅读 · 维度爆炸 / 抽象视角 / 通向第 6 讲

本章把维度爆炸展开：三维及以上费用背包不是「算法不够好」，而是状态空间本身的体积爆炸；工业 SaaS 调度器面对它所用的标准技术，与教科书 DP 已分道扬镳。随后给出「复整数域上的背包」这一抽象视角，把整个维度家族在数学上统一，最后衔接第 6 讲分组背包。

4.1 · 一 · 维度爆炸 · 三维及以上费用的工程方案

为什么「再加一维」就不可行

二维 01 背包 $O(NVU)$ 在各维 ~10³ 时已接近主流硬件单秒计算量极限（10⁸ 量级）。加第三维，时间 $O(NVUR)$ → 10¹¹，空间 $O(VUR)$ → 10⁹ 字节（约 4 GB）——二者同时越过工程可行线。这不是「算法不够好」，而是状态空间本身的体积爆炸：任何忠实记录每个状态的方法都跑不动。这也是为何「伪多项式 + 多维」在 d ≥ 3 时事实上等价于「指数难」。

三维费用并不少见 · 五个真实场景

「三维约束远比二维稀少」这一直觉是错的。下列每一个都是真实的三维（或更高维）资源调度问题，把任一维硬性砍掉都会引入业务上不可接受的副作用：

容器编排 · Kubernetes / AWS ECS / Borg:CPU + 内存 + GPU（或网络带宽 / 本地磁盘 IOPS）。砍掉任一维都会导致容器 OOM 或调度失衡。
跨境物流装箱：重量 + 体积 + 件数上限（海关 / 监管的「申报件数」硬性约束）。件数维由法规给出，不可压。
投资组合：预算 + 风险敞口（VaR 或 Beta）+ 流动性下限。监管框架(Basel III、Solvency II)要求三维同时合规。
多媒体编码 ABR：比特率 + 帧率 + 缓冲区水位。任一维超标都直接表现为播放卡顿或画质回退。
数据库查询规划：内存(work_mem)+ I/O（共享缓存）+ CPU 时间片。查询优化器在三维上挑选执行计划。

六类标准技术 · 按工业实践优先级排序

按「Kubernetes scheduler / Borg / 商业 ILP solver(Gurobi、CPLEX)的实际使用频率」排序。前三项是工程默认手段，后三项偏学术或特定场景：

#	技术	何时用	复杂度变化
1	降维 / 消维	某维冗余、强相关或可事后过滤	d → d−1
2	离散化粗化	某维允许牺牲精度(~10×)	NVUR → NVU(R/10)
3	拉格朗日松弛	第 d 维是「软约束」（允许 ±ε 偏差）	O(NVU·logV)
4	分支定界 B&B	状态稀疏，实际只展开 promising 子集	实测 ≪ NVUR
5	PTAS / 常数近似	学术或合规要求「有近似保证」	多项式 + ε
6	元启发式 GA / SA / ALNS	只需「足够好」，不需最优——工业实际首选	工程实测 ms-s 级

降维 · 最廉价的「加速」

冗余维：若 ΣEᵢ ≤ R 对所有物品成立，该维永不触发，直接删。
强相关维:K8s 中 CPU 与内存的 request 往往按「规格档」配比（1:2、1:4 等），可合并为一维「档位」，d → d−1。
事后 Pareto 过滤：先 DP 其他两维出 Pareto 前沿（典型大小远小于 V×U），再扫一遍筛 R 约束。这是「先松弛、后剪枝」的方法论。

离散化粗化 · 用精度换可行性

把第三维 R 由 10³ 桶降到 10 桶（对数刻度或分位数），复杂度立即除 100。Kubernetes scheduler 实际就是按「node label / resource class」做粗粒度匹配，而非精确到 mCPU——这是「维度粗化」在工业上的隐式应用。代价是某些边界情形可能被舍入到次优解，但工业级编排允许这种舍入。

拉格朗日松弛 · 多维背包的工程事实标准

把第 3 维硬约束改为软惩罚，引入拉格朗日乘子 λ:

maximize  Σ (W_i - λ·E_i) x_i
subject to  Σ C_i x_i ≤ V,  Σ D_i x_i ≤ U
            x_i ∈ {0, 1}

内层仍是二维 DP $O(NVU)$ ；外层对 λ 二分搜索（找使 ΣEᵢxᵢ ≈ R 的 λ*），总复杂度 $O(NVU\cdot logV)$ 。代价：找到的解可能违反 R 约束 ±ε，适合「允许软偏差」的场景。这是商业 MILP solver(Gurobi、CPLEX)在多维背包子问题上的标准启发式，也是 Fisher 1981 综述以来文献的事实标准。

分支定界 · 状态稀疏时的有效方法

LP 松弛给出上界，启发式（贪心 / 局部搜索）给出下界。展开分支前先看上界是否小于当前最优——若小，整条分支直接剪。Pisinger 的 expknap / minknap 类算法可推广到多维(multidim B&B)，实际跑得很快，但最坏情况仍指数。适合状态分布稀疏、目标函数 LP 松弛 gap 小的实例。

PTAS / 常数近似 · 学术保证

多维 0-1 背包是 strongly NP-hard：不存在 FPTAS（除非 P = NP）；但存在 PTAS，在多项式时间内给出 (1−ε) 倍最优近似——见 Chekuri & Khanna 2005。常数因子近似 (1−1/e) 通过 LP rounding 也常见。学术合规需要「可证明的误差上界」时用，工业中较少。

元启发式 · 工业 SaaS 的实际选择

工业级调度器大量在用以下三类元启发式，它们无最优性保证，但响应时间在 ms-s 级别，适合实时调度：

遗传算法 GA：物品子集编码为 bitmap，交叉变异选优。
模拟退火 SA：在子集空间内随机游走，接受退化解避免陷入局部最优。
ALNS(Adaptive Large Neighborhood Search)：选择性破坏 + 修复；Kubernetes scheduler 底层做的就是 ALNS 变体——每次调度新 Pod 不重做全局优化，而是局部破坏 + 重修。

实用判定表 · 你的场景选哪一种

你的场景	推荐技术
三维以下，各维 ≤ 10³	直接 DP，无需妥协
三维，各维 ~10³	降维（优先）→ 拉格朗日松弛
四维及以上	元启发式（工业）/ 分支定界 + 近似（学术）
强实时（< 100 ms 响应）	元启发式 + 解缓存
离线批量（分钟级）	拉格朗日松弛 / 商业 ILP solver(Gurobi、CBC)

本讲的二维 DP 演示给出了「忠实记录每个状态」的精确方法；一旦进入三维及以上，教科书 DP 与工业实践之间出现明显的分水岭——这条分水岭不是技术高低，而是「是否能容忍最优性损失」的工程决策。读者在选型时，先问「业务能否接受 ±ε 偏差」，再选具体技术。

4.2 · 二 · 抽象视角 · 复整数域上的背包

「复整数域上的背包」是把维度家族统一到数学结构上的视角：将一维背包视作自然数 ℕ 上的问题，则二维背包对应 ℕ²（可视为格点格子）,d 维背包对应 ℕᵈ。这一视角使一维的全部技术（循环方向、空间压缩、初始化约定）在更高维度上自然推广。

状态转移方程的向量化

记物品费用向量 $\vec{c}_i = (C_i, D_i, E_i, \dots )$ 、容量向量 $\vec{v} = (v, u, r, \dots )$ ，则状态转移方程统一为

F[i, v⃗] = max{ F[i-1, v⃗],  F[i-1, v⃗ - c⃗_i] + W_i }

其中 $\vec{v} - \vec{c}_i$ 是向量减法（要求每个分量都非负，否则取分支无效）。这一向量形式与维度无关——一维、二维、d 维，方程的结构完全一致。

循环方向规则的维度无关性

对 01 背包，所有维度均双逆序循环（v 从 V 递减、u 从 U 递减、r 从 R 递减……）；对完全背包，所有维度均正序循环。规则与维度数无关——这正是从一维到 d 维「无需重新推导」的数学保证。

空间压缩的维度无关性

滚动掉 i 维，保留高维数组 $F[\vec{v}]$ ，空间由 $O(N\cdot |\vec{V}|)$ 降至 $O(|\vec{V}|)$ ，其中 $|\vec{V}| = V\cdot U\cdot R\cdots$ 是状态空间的体积。压缩规则与维度数无关——这也是为何「再加一维」在算法层面不需要重写，只需把数组多开一维。但工程层面崩在体积上，这正是维度爆炸的本质。

从向量公式到 JavaScript 实现 · 任意 d 维通用版

上面的「维度无关性」是论证，下面给出对应的算法实证：一个把维度从硬编码升级为参数的通用 d 维背包实现。物品的费用从标量 C 变为向量 C⃗[]，容量上限从二元 (V, U) 变为数组 caps；状态空间用一维 Float64Array 扁平化承载，通过 strides 数组做多维索引（NumPy / ndarray / 张量库的通用布局技巧）。d 层嵌套循环由递归动态展开，而非静态嵌套 for。

关键技术点

strides 多维索引:d 维坐标 (c₁, …, c_d) 映射到扁平索引 Σ cᵢ·sᵢ，其中 sᵢ = ∏_{j>i}(capⱼ+1)。这是 NumPy 的 ndarray.strides 布局，也是张量库内存模型的基础。
递归展开嵌套:d 不是编译时常量，不能写 d 层静态 for；改用递归——每层 rec(dim) 处理一个维度，直到 dim === d 时执行最内层更新。
双逆序的维度无关性：每个 rec(dim) 都做双逆序（从 caps[dim] 递减到 item.C[dim]）——这正是上文「循环方向规则的维度无关性」的算法实证。
Float64Array vs Array：扁平化用 Float64Array(typed array)替代普通 Array 与多层嵌套，内存连续、JIT 友好，这是工程实现的标准做法。

实证结果 · 算法 trivially 通用，工程崩在体积上

以同一份 knapND 跑 d = 1, 2, 3 三种维度（各维都用小数据），三组结果都正确（可点 ▶ 运行验证）。但通用版相对于手写 knap2D 有约 7× 的常数代价（扁平索引计算 + 递归调用栈）——这在小数据上可忽略，但提醒读者：工程实现中维度数固定时仍倾向手写嵌套，通用版多用于研究 / 探索阶段。

更根本的限制是状态空间体积 $|\vec{V}| = \prod _i(cap_i+1)$ :

d	各维上限	状态空间体积	时间估算 O（N·体积）	可行性
1	V = 10³	10³	10⁵	✓
2	V = U = 10³	10⁶	10⁸	✓ （本讲边界）
3	V = U = R = 10³	10⁹	10¹¹	✗ 时间与空间同时超限
4	各 10³	10¹²	10¹⁴	✗ 物理不可能

这表是维度爆炸的算法实证：把 knapND 的 d 从 2 调到 3 时，代码一字未改，但状态空间从 10⁶ 跳到 10⁹——这才是为什么三维以上需要拉格朗日松弛、元启发式等替代手段。算法的通用性是廉价的，状态空间的体积才是真正的天花板。

4.3 · 三 · 通向第 6 讲 · 分组背包

第 6 讲将转向分组背包：物品被划分为若干组，每组至多选取一件。届时虽然状态仍为 $F[v]$ （回归一维），但循环结构将由两层（物品、容量）变为三层（组、容量、组内物品），且循环顺序本身即决定算法的正确性——错位的循环嵌套会让「每组至多一件」退化为「每组任意件」，这与本讲的二维费用形成有趣对照：本讲是状态维度多了一维，而第 6 讲是循环维度多了一层。两种「加一维」的工程后果截然不同。