0-1 背包
0-1 背包问题是什么？
- 条件:
n件物品, 背包重量上限cap; 第i件物品重量wgt[i], 价值val[i]; - 限制: 每件物品最多选一次;
- 目标: 求装入物品的最大总价值;
- 阶段: 按物品序号推进, 每阶段把重量维度填满;
状态与转移方程如何写？
- 状态:
dp[i][c]为前i件物品放入容量c的背包能获得的最大价值; - 决策: 只考虑第
i件物品, 选或不选;- 不选:
dp[i][c] = dp[i-1][c]; - 选: 需
wgt[i-1] <= c,dp[i][c] = dp[i-1][c - wgt[i-1]] + val[i-1];
- 不选:
- 方程:
dp[i][c] = max(dp[i-1][c], dp[i-1][c - wgt[i-1]] + val[i-1]); - 初值: 没有物品或容量为 0 时价值为 0, 即
dp[0][*] = dp[*][0] = 0; - 答案:
dp[n][cap]; - 复杂度: 时间
O(n * cap), 空间O(n * cap);
const knapsackDP = (wgt, val, cap) => {
const n = wgt.length;
const dp = Array.from({ length: n + 1 }, () => new Array(cap + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let c = 0; c <= cap; c++) {
if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c];
else dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
}
}
return dp[n][cap];
};
滚动数组为什么必须倒序遍历？
- 依赖: 每个状态只和上一行 (
dp[i-1]) 的同列与左列有关, 一行即可放下全部信息; - 一维写法:
dp[c] = max(dp[c], dp[c - wgt[i-1]] + val[i-1]); - 倒序原因:
dp[c - wgt]必须是上一行的旧值; 正序遍历会被本轮刚写入的值覆盖, 等价于物品可重复选; - 复杂度: 时间
O(n * cap), 空间O(cap);
const knapsackDPComp = (wgt, val, cap) => {
const dp = new Array(cap + 1).fill(0);
for (let i = 1; i <= wgt.length; i++) {
for (let c = cap; c >= wgt[i - 1]; c--) {
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
return dp[cap];
};