二维(01)背包问题
其可描述为“设物品序列中每个物品只有1个，物品\(i\)有2个费用属性\(x_i,y_i\)，有1个价值属性\(w_i\)。给定2个正整数\(U,V\)，求物品组合使\(\sum x_k \leq U \)与\(\sum y_k \leq V \)时，\(\sum w_k\)最大”。形象一点来说就是背包除了体积限制，还有重量限制。
问题的状态转移方程是\(F(i,u,v) = max\{~ F(k-1,u-x_i,v-y_i)+w_i, F(k-1,u,v) ~ \} \)，参考(01)背包的思路很容易找到和证明该方程。问题的一个边界是\(u-x_i<0\)或\(v-y_i<0\)取\(F(i,u,v) = F(k-1,u,v) \)。下面给出用动态规划求解出\(F(i,u,v)\)的步骤，并且不讨论如何用求出来的\(F\)得到具体解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def dp(x, y, U, V, w): f = [ [ [0 for j in range(V + 1)] for j in range(U + 1)] for i in x] for i in range(len(x)): for j in range(U + 1): for k in range(V + 1): if i == 0: if (j - x[i] < 0 or k - y[i] < 0): f[i][j][k] = 0 else: f[i][j][k] = w[i] else: if (j - x[i] < 0 or k - y[i] < 0): f[i][j][k] = f[i - 1][j][k] else: f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - x[i]][k - y[i]] + w[i]) return f |