01 背包¶

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

例如，背包最大重量为 4，物品为

	重量	价值
物品 `0`	1	15
物品 `1`	3	20
物品 `2`	4	30

暴力¶

每个物品只有选和不选两种状态，可以暴力枚举所有情况，时间复杂度为 \(O(2^n)\)。

二维 dp¶

用 dp[i][j] 表示：从物品 0 到物品 i 中选取，放入容量为 j 的背包中，能得到的最大价值。

`dp[i][j]`	`1`	`2`	`3`	`4`
`0`	15	15	15	15
`1`	15	15	20	35
`2`	15	15	20	35

当背包容量为 j 时，对于第 i 个物品，只有选和不选两种情况

如果不选，总价值为 dp[i-1][j]
如果选，则先放其他物品并空出 weight[i] ，最后再放物品 i，总价值为 dp[i-1][j-weight[i]] + value[i]

总结一下，状态转移方程为

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);

dp[i][j] 依赖上一行 dp[i-1][] 的值，所以 dp 表的第一行必须手动初始化。

// j < weight[0] 时 dp[0][j] 都是 0
for (int j = weight[0]; j <= bagweight; j++)
{
    dp[0][j] = value[0];
}

完整代码

vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

// j < weight[0] 已在上方被初始化为 0
for (int j = weight[0]; j <= bagweight; j++)
{
    dp[0][j] = value[0];
}

for (int i = 1; i < weight.size(); i++) // 物品，从 1 开始
{
    for (int j = 0; j <= bagweight; j++) // 遍历背包容量，注意 j 的范围
    {
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

最终结果是 dp[n-1][bagweight]。

一维 dp¶

注意到状态转移方程中 dp[i][] 只和上一行 dp[i-1][] 有关，所以可用滚动数组优化。

dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);

dp 数组要根据题意初始化。前面举的例子里，所有物品的价值都是正的，一开始什么物品都没放，所以 dp 数组初始化为 0。

vector<int> dp(bagweight + 1, 0);

for (int i = 0; i < weight.size(); i++) // 物品
{
    for (int j = bagweight; j >= weight[i]; j--) // 倒着遍历背包容量
    {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

最终结果是 dp.back()。还有几点要注意：

因为 dp[j] 依赖前面的元素 dp[j-weight[i]]，所以 j 这个维度（背包容量）要从大到小遍历。
两个 for 循环不能交换。因为 j 是从大到小遍历的，如果交换两个 for 循环的话，dp[j-weight[i]] 总是初始值 0，状态转移方程就变成 dp[j] = max(dp[j], value[i])，导致背包中至多只有一个物品。

参考¶

反向链接

完全背包