二维费用的背包问题

【问题描述】有 n 件物品和一个容量为 C、容积为 U 的背包。第 i 件物品的重量是 w[i]，体积是 u[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。

(1) 0/1背包的表示方法

费用加了一维，只需把状态也加一维。

1. 状态表示：设 f[i][c][u]为前 i 件物品付出两种代价分别为 c 和 u 时可以获得的最大价值。

ìf[i－1][c][u]

2. 状态转移方程：f[i][c][u]＝maxíîf[i－1][c－w[i]][u－u[i]]＋v[i]

当然，为了节省空间，可以把 i 去掉。

3. 一个启示：当发现由熟悉的动态规划题目变形而来的题目时，在原来的状态中加一维以满足新的限制，这是一种比较通用的方法。

(2) 限制物品总个数的0/1背包

【问题描述】有 n 件物品和一个容量为 C 背包。第 i 件物品的重量是 w[i]，价值是 v[i]。现在要求转入背包的物品个数不超过 M。求解将哪些物品装入背包可使价值总和最大。

只需把问题变一下——有 N 件物品和一个容量为 C、容积为 M 的背包。第 i 件物品的重量是 w[i]，体积是1，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。

把最大个数看做一种容积就可以了。

(3) 二维费用的完全背包和多重背包问题

循环时仍然按照完全背包（顺序循环）和多重背包（分割）的方法操作，只不过比完全背包和多重背包多了一维。

(4) 二维费用背包的另一种解法

把背包的容量和费用看作一个复数。详见《背包九讲》。