多维背包问题

多维背包问题（multidimensional knapsack problem）要求选择一批不可拆分的物品，使总收益最大，同时不超过多种资源的容量。这里的“维”指资源约束数量，例如重量、体积与预算，并不一定指物品在空间中的几何维度。

一辆车的重量与体积容量都为五。四件货A、B、C、D的“重量、体积、收益”依次为 $(4,1,6)$、$(1,4,6)$、$(3,3,9)$、$(2,2,5)$。若只限制重量，B+C可得十五，但体积为七，不能装车；若同时检查两项资源，C+D恰好用满五、五，收益十四。

多条资源约束

对 $n$ 件物品与 $d$ 种资源，令 $a_{ki}\ge 0$ 为物品 $i$ 消耗的第 $k$ 种资源，$b_k\ge 0$ 为相同单位的容量，$v_i$ 为收益。模型为 $$\begin{array}{cc}max& \sum _{i=1}^n{v}_i{x}_i,\\ \sum _{i=1}^n{a}_{ki}{x}_i& \le b_k(k=1,\dots ,d),\\ x_i& \in \{0,1\}.\end{array}$$ 每一行可以有自己的单位，但同一行内消耗与容量必须一致。重量和体积不能直接相加成为一个物理量；加权合成一条约束可以提供某种松弛界，通常不能代替全部原约束。

主例中可行的双件组合只有A+B与C+D，收益分别十二、十四；其余双件至少一种资源超限。任意三件的重量和或体积和也会超限，四件更不行。单件最大收益为九，所以C+D的十四就是全局最优。

横纵坐标分别为重量与体积消耗。资源位置相同的两个方案仍有不同收益，因此动态规划在同一资源状态下保留最大收益。

二维整数容量的递推

容量及消耗为非负整数时，定义 $F(i,u,v)$ 为只用前 $i$ 件、两种容量分别不超过 $u,v$ 的最优收益。最后一件只有不选或选入两种情况，把两种候选收益分别记为 $V_0,V_1$： $$\begin{array}{cc}{V}_0& =F(i-1,u,v),\\ V_1& =v_i+F(i-1,u-a_{1i},v-a_{2i}),\\ F(i,u,v)& =max\{V_0,V_1\}.\end{array}$$ 第二候选 $V_1$ 只在两种剩余容量非负时存在，初值为 $F(0,u,v)=0$。任何合法选择必归入一支，而每支最优子集接上当前决策仍合法，因此按物品数归纳可证明递推。

代码用记忆化保存实际访问的状态，再比较相邻层值回溯选择。输入消耗按“每件一个二元组”给出；收益允许负值，空选择仍合法。

Python 3

from functools import lru_cache
import math

def knapsack_2d(resources, values, capacity):
    a, value, cap = tuple(map(tuple, resources)), tuple(values), tuple(capacity)
    if len(cap) != 2 or any(type(b) is not int or b < 0 for b in cap):
        raise ValueError("two nonnegative integer capacities required")
    if len(a) != len(value) or any(len(row) != 2 for row in a):
        raise ValueError("matching two-resource items required")
    if any(type(x) is not int or x < 0 for row in a for x in row):
        raise ValueError("nonnegative integer resource use required")
    if any(not math.isfinite(x) for x in value):
        raise ValueError("finite values required")
    @lru_cache(None)
    def f(i, u, v):
        if i == 0:
            return 0
        best = f(i-1, u, v)
        r, s = a[i-1]
        if r <= u and s <= v:
            best = max(best, value[i-1] + f(i-1, u-r, v-s))
        return best
    u, v = cap
    best, chosen = f(len(a), u, v), []
    for i in range(len(a), 0, -1):
        if f(i,u,v) > f(i-1,u,v):
            chosen.append(i-1); u -= a[i-1][0]; v -= a[i-1][1]
    return best, tuple(reversed(chosen))

print(knapsack_2d([(4,1),(1,4),(3,3),(2,2)], [6,6,9,5], (5,5)))
# (14, (2, 3))

固定两维时最多有 $(n+1)(b_1+1)(b_2+1)$ 个状态，每状态常数次转移，故时间、记忆表空间均为 $O(n(b_1+1)(b_2+1))$。这是对容量数值的伪多项式界；容量写成二进制后的位数很小时，数值仍可能很大。维数继续增加时，容量网格的乘积会迅速膨胀。

变式。 体积容量降为四、重量仍为五。A+B与C+D都因体积五失效，其余双件也不可行，最优单选C，收益九。若某件消耗为零、收益为正，它应被选一次，代码通过物品层数递减保证不会无限重复；若允许每件无限次选择，则变成另一种整数背包，递推不能照搬。