跳转至

完全背包

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

二维 dp

和 01 背包 类似，用 dp[i][j] 表示：从物品 0 到物品 i 中选取，放入容量为 j 的背包中，能得到的最大价值。当背包容量为 j 时，对于第 i 个物品，只有选和不选两种情况，但物品 i 现在可以无限重复放入

  • 如果不选，总价值为 dp[i-1][j]
  • 如果选，则先空出 weight[i]，从 0 到 i 中选物品放入背包，最后再放一个物品 i，总价值为 dp[i][j-weight[i]] + value[i]

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

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

一维 dp

状态转移方程可以压缩为

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

完整代码

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

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

最终结果是 dp.back()。要注意 j 这个维度（背包容量）是从小到大遍历的。

排列组合

必须明确求物品的排列还是组合，这决定了两个 for 循环的先后。上面的例子，看成排列或组合都行，所以两个 for 循环可以交换。

下面，以求能装满背包的物品组合数/排列数为例。用 dp[j] 表示背包容量为 j 时的组合数/排列数。状态转移方程为

dp[j] += dp[j-weight[i]];

dp[0] 必须初始化为 1，这样当 j == weight[i] 时，上式相当于 dp[j] += 1。dp 的其他元素初始化为 0。

组合数

外层遍历物品，内层遍历背包容量。

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

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

如果物品 u < v，在放入背包时，一定先放 u 再放 v，所以算的是组合数。

排列数

外层遍历背包容量，内层遍历物品。

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

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

如果物品 u < v，在放入背包时，既统计了 [u, v] 又统计了 [v, u]，所以算的是排列数。

像 139. 单词拆分 - 力扣（LeetCode） 这题，因为字符串拼接不满足交换律，所以实际求的是排列。

参考