二维费用背包

先看一个具体场景：你有 2 件物品，但背包这次卡的不是一条约束，而是两条， 物品 1 占「费用1 $a=1$、费用2 $b=2$」，价值 $v=3$；物品 2 占「$a=2,b=1$」，价值 $v=4$。 背包要求：费用1 之和 $\le A=4$，同时费用2 之和 $\le B=4$。两条线都不能越界。

这类约束在现实里遍地都是：买东西受钱和时间双重限制；装货受体积和质量双重限制；组队受预算和人数双重限制。 共同点是，每选一件，就要同时从两个「口袋」里各扣一笔，而且两个口袋互不相通：省下的时间换不来更多钱。

能不能只盯着一种费用做普通 01 背包，事后再检查另一种够不够？不行。因为「费用1 最省」的方案，费用2 未必也最省，两种费用的取舍是耦合的，必须一起进 DP 的状态，才知道某个费用1 的档位下、费用2 还剩多少空间。

回忆 01 背包的一维状态 $f[j]$：花费不超过 $j$ 时的最大价值。现在费用有两种，那就让状态同时记住两笔账： 设 $dp[x][y]$ 表示费用1 不超过 $x$、费用2 不超过 $y$ 时能取得的最大价值。约束从一条数轴变成一整片平面，下标也从一个变成一对。

转移和 01 背包一模一样的两条路，只是「扣费用」这一步要同时扣两种：

不取第 $i$ 件：它没参与，$dp[x][y]$ 保持原值（还没装它时的最优）。

取第 $i$ 件（前提两种费用都够：$x\ge a_i$ 且 $y\ge b_i$）：费用1 腾出 $a_i$、费用2 腾出 $b_i$，剩下的 $(x-a_i,\ y-b_i)$ 空间留给前面的物品去最优，再补上它的价值 $v_i$，即 $dp[x-a_i][y-b_i]+v_i$。

两条路取较大者，就得到转移方程（写成一维滚动数组的形式）：

边界：$dp[x][y]=0$（一件不装，价值为 0）。答案：$dp[A][B]$。对照 01 背包一维式 $f[j]=\max(f[j],\ f[j-w_i]+v_i)$， 二维费用只是把「一个下标 $j$、扣一种费用 $w$」换成「两个下标 $x,y$、同时扣两种费用 $a,b$」，方程骨架分毫未动。

用开头的例子（物品 $(a,b,v)=(1,2,3),\ (2,1,4)$，上限 $A=B=4$）走几步，重点盯住每装一件，两种费用一起扣：

注意演示里每处理一件，就把整张表刷一遍：能装下该件（$x\ge a,\ y\ge b$）且更划算的格被抬高，其余不动。 这正是一维滚动写法的样子，只保留「当前这张二维表」，逐件在它上面就地更新。

变形一：价值恒 1，求「最多能选几件」。 很多题不问最大价值，而问「预算和时间都有限，最多能实现几个愿望 / 塞下几样东西」。 这只需把每件的价值统一设成 1，转移里的 $+v_i$ 变成 $+1$，$dp[x][y]$ 的含义就从「最大价值」变成「最多件数」：

「求个数」和「求价值」在背包里本是同一台机器，把价值当成 1 计，最大价值就是最多件数。下面例题 P1855 正是这一路。

变形二：把「二维」看成「朴素三属性物品」。 二维费用听着抽象，落到代码里不过是每件物品多带一个属性、循环多套一层。 像 P1507 那样「每份食物有体积、质量、卡路里」，体积和质量是两种费用，卡路里是价值，直接当普通 01 物品处理，只是背包状态是二维的 $dp[j][k]$ 而已。

至于循环方向：一维滚动写法里，两种费用维都要倒序（$x$ 从 $A$ 到 $a$、$y$ 从 $B$ 到 $b$）。道理和 01 背包「必须倒序」完全一致：倒序时 $dp[x-a][y-b]$ 用的是本件尚未装入的旧值，才能保证每件至多取一次。三层循环的骨架是「逐件 → 费用1 倒序 → 费用2 倒序」：

for 每件物品 (a, v, b):
  for x = A downto a:        // ★费用1 维倒序
    for y = B downto b:      // ★费用2 维倒序
      dp[x][y] = max( dp[x][y], dp[x − a][y − b] + v )