大家好，我是前端西瓜哥。
在阅读本文之前，建议先看看我的另一篇文章（只关注 “重量” 一个维度）：
《动态规划模型：0-1背包问题》
背包二维费用问题，是在原本 “重量” 的单一维度上，加上 “价值” 维度。
有 n 个物品，它们的重量为 weight[i]，对应的价值为 value[i]，在不超过背包总重量 w 的情况下，求能装入的最大价值。
需要定义类型为 number 的二维数组，范围为 [n][w 1]。
dp[i][j] 表示决策完第 i 个物品后，重量变成 j 时，能装入的最大价值。
动态转移方程为：
代码语言：javascript复制// 不放入 放入（所以要将第 i 个物品的价值计入）
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] value[i]);
代码实现：
代码语言：javascript复制export function knapsackMaxValue(weight: number[], value: number[], w: number): number {
const n = weight.length;
// 初始化 number 类型的二维数组，范围：[n][w 1]
const dp: number[][] = new Array(n);
for (let i = 0; i < n; i ) {
dp[i] = new Array(w 1).fill(0);
}
dp[0][0] = 0; // 不装入
if (weight[0] <= w) { // 装入 weight[0]，不能越界。
dp[0][weight[0]] = value[0]; // 装入第一个
}
for (let i = 1; i < n; i ) {
for (let j = 0; j <= w; j ) {
dp[i][j] = dp[i - 1][j];
if (j - weight[i] >= 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
}
}
}
let max = 0;
for (let j = 0; j <= w; j ) {
max = Math.max(max, dp[n - 1][j]);
}
return max;
// 上面这样写是为了照顾其他语言的读者，可以直接用 Math.max(...dp[n - 1])，更优雅一些
}
源码已经放到 GitHub 上，地址为：
https://github.com/F-star/dynamic-programming-play/blob/master/src/knapsack/knapsack_01/knapsack_01.ts#L151
可以通过 npx jest 命令进行单元测试。
结尾
二维费用问题，需要将值用来保存最大价格，并在更新状态时做装入和不装入两种情况的比较，取其中比较大的。
我是前端西瓜哥，欢迎关注我，学习更多前端知识。
