算法题动态规划 01 背包

递推公式:

// dp[i][j] 表示从下标为 [0-i] 的物品里任意取, 
// 放进容量为 j 的背包, 价值总和的最大值是 dp[i][j]
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

max(..., ...) 表示两种情况, 要么不选当前物品 i 放入背包, 要么选

若不把当前物品 i 放入背包, 背包的总价值为第 i-1 个物品时, 背包的状态, 即被包容量为 j, 从 0 ~ i-1 任选放入, 价值为 dp[i - 1][j]
选的话背包的总价值为物品 i 的价值加上背包减去物品 i 的重量后, 在第 i-1 个物品的状态, 即 dp[i - 1][j - weight[i]] + value[i]

因为可以把 dp[i - 1] 那一层拷贝到 dp[i] 上, 表达式完全可以是：

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

即计算物品 i 的情况时, 不用再去看上一层(物品)的情况, 看当前就行了, 所以直接就可以把 [i] 去掉, 得到:

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

dp[j]: 相当于二维 dp 数组中的 dp[i-1][j]，即不放物品 i
dp[j - weight[i]] + value[i]: 就是放物品 i

最后代码可以得到:

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]);
    }
}

即对于每个物品, 我们都要从背包的最大容量开始到容量等于物品 i 的重量结束, 尝试去放物品 i, 比如我们有 3 个物品, 价值为 [10, 20, 50], 重量为 [4, 2, 6], 背包容量为 6, 此时我们从第一个物品开始尝试:

如果背包容量为 6 , 第一个物品放还是不放, 看哪个情况背包总价值大, 显然放入, 价值变大, 因为刚开始为 dp[6] = 0, 所以我们得到 dp[6] = dp[2] + value[0] = 0 + 10 = 10
然后我们尝试如果背包容量为 5 , 第一个物品放还是不放, 类似第一种情况, 我们得到: dp[5] = dp[1] + value[0] = 0 + 10 = 10
与上面相同, 如果背包容量为 4, 背包总价值也是 10, 之后我们就不尝试了, 因为如果背包容量小于 4, 根本放不进去第一个物品, 所以默认此时以及之后的总价值为 0,

然后我们尝试第二个物品, 对于第二个物品, 同样从背包容量为 6 开始尝试:

如果背包容量为 6, 第二个物品放还是不放, 比较这两种情况下背包的总价值, 此时，放入第二个物品后, dp[6] = dp[4] + value[1] = 10 + 20 = 30, 总价值变大了, 所以我们更新 dp[6] = 30
接着尝试背包容量为 5，同样比较放入或不放入的情况。放入第二个物品后，dp[5] = dp[3] + value[1] = 0 + 20 = 20，而之前 dp[5] = 10，因此更新 dp[5] = 20
以此类推, 背包容量为 2 时，放入第二个物品后，dp[2] = dp[0] + value[1] = 0 + 20 = 20，更新 dp[2] = 20。
背包容量小于 2 时无法放入第二个物品，因此对应的 dp 值不变

最后，我们尝试第三个物品：

如果背包容量为 6, 第三个物品放还是不放, 放入第三个物品后，dp[6] = dp[0] + value[2] = 0 + 50 = 50，而之前 dp[6] = 30，因此更新 dp[6] = 50
背包容量为 5 或更小的情况时，第三个物品的重量（6）已经超过当前容量，无法放入，因此对应的 dp 值保持不变

这里我们选择倒序遍历是为了避免同一个物品被放入两次, 还以上面例子为例, 我们尝试放第一个物品,

刚开始我们假设背包容量为 0, 1, 2, 3 此时不能放下第一个物品, 因此 dp[0~3] = 0
如果背包容量为 1, 此时也不能发下第一个物品, 然后被包容量为 2, 3, 都是相同情况, 所以 dp[0~4] = 0
如果背包容量为 4, 此时可以放下第一个物品, 放还是不放呢, 比较 dp[4] 和 dp[4 - weight[0]] + value[0], 显然要放, 因为 dp[4] 现在还为 0, 所以我们选择 dp[4] = dp[4 - weight[0]] + value[0] = dp[0] + value[0] = 10
…

此时 dp[0~6] 的值为: 0, 0, 0, 0, 10, 10, 10, 这都没什么问题, 接下来我们来尝试放第二个物品,

刚开始背包容量为 0, 1, 放不下, 所以我们从背包容量为 2 开始
如果背包容量为 2，比较 dp[2] 和 dp[2 - weight[1]] + value[1]，即 dp[2] 和 dp[0] + value[1]
- 我们遍历第一个物品的时候, dp[0~3] = 0, 所以此时 dp[2]=0
- 若我们选择放入 dp[2], 放入后 dp[2] = dp[0] + value[1] = 0 + 20 = 20，更新 dp[2] = 20
如果背包容量为 3，与上面相同, 此时我们判断放还是不放第二个物品
- 不放第二个物品, dp[3] = dp[3] = 0
- 放第二个物品，dp[3] = dp[3 - weight[1]] + value[1] = dp[1] + value[1] = 0 + 20 = 20，更新 dp[3] = 20

注意此时 dp[0~6] 的值为: 0, 0, 20, 20, 10, 10, 10,

如果背包容量为 4
- 不放第二个物品, dp[4] = 10, 我们遍历第一个物品时, 更新了这个值,
- 放第二个物品，dp[4] = dp[4 - weight[1]] + value[1] = dp[2] + value[1] = 20 + 20 = 40。由于之前的 dp[4] = 10，我们选择更新 dp[4] = 40

有没有发现, 此时我们把第二个物品放入了两次, 因为 dp[2] = 20 的值就是这轮循环(尝试放第二个物品)中前面通过放入第二个物品得来的, 现在只是容量变大了, 我们又放一次第二个物品, 即 value[1] 和 dp[2] 相加, 这不就是重复了吗,

或者说我们的算法的本质后面的状态又是根据前面的状态推断出来的, 也就是公式 dp[j] = dp[j - weight[i]] + value[i]) 的问题, 因为 j - weight[i] 一定比 j 小嘛,

此时我们还按背包容量从小到大遍历, 那对于同一个物品, 后面就有可能遇到背包已经放了这个物品的状态, 此时再和物品 value 相加, 就重复了, 所以我们要从后往前, 这样, 可以保证前面的状态肯定没有放过当前物品, 注意这里前面的状态指的是, 背包的容量比较小的状态,

比如对于容量为 4 来说, 0, 1, 2, 3, 就是前面的状态, 所以对于同一个物品, 当我们从背包容量 4 遍历到背包容量 0 使用我们的递推公式来分别计算背包容量为 4, 3, 2, 1, 0 时的价值, dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);, 肯定不会遇到, 已经放了当前物品已经被放过的状态, 因为 dp[j] = dp[j - weight[i]] + value[i]) 中, j - weight[i] 一定比 j 小,

算法题 动态规划 01 背包

算法题动态规划 01 背包