目录
- 一、引言
- 二、0 - 1 背包问题概述
- 2.1 问题定义
- 2.2 具体示例
- 三、动态规划与滚动数组思路
- 3.1 二维动态规划思路
- 3.2 滚动数组优化思路
- 四、具体分析全过程
- 4.1 初始化 `dp` 数组
- 4.2 考虑物品 0（重量为 1，价值为 15）
- 4.2.1 当 `j = 4`
- 4.2.2 当 `j = 3`
- 4.2.3 当 `j = 2`
- 4.2.4 当 `j = 1`
- 4.3 考虑物品 1（重量为 3，价值为 20）
- 4.3.1 当 `j = 4`
- 4.3.2 当 `j = 3`
- 4.4 考虑物品 2（重量为 4，价值为 30）
- 4.4.1 当 `j = 4`
- 五、代码实现
- 六、代码解释
- 6.1 初始化部分
- 6.2 双重循环部分
- 6.3 输出部分
- 七、复杂度分析
- 7.1 时间复杂度
- 7.2 空间复杂度
- 八、总结
一、引言
背包问题是数据结构中的经典问题，也是且具有挑战性的问题之一。而 0 - 1 背包问题更是基础中的基础，它在众多实际场景里都有广泛的应用，例如资源分配、货物装载等。在解决 0 - 1 背包问题时，动态规划是一种常用且高效的方法。本文将详细探讨 0 - 1 背包问题，并深入介绍如何使用滚动数组对其进行优化。
二、0 - 1 背包问题概述
2.1 问题定义
给定一组物品，每个物品都有对应的重量和价值，同时有一个具有最大容量限制的背包。在每个物品只能选择放入或不放入背包的规则下，我们需要找出一种物品组合，使得背包内物品的总价值达到最大。
2.2 具体示例
为了更直观地理解问题，我们来看一个具体的例子。有以下物品信息和背包容量：
| 物品编号 | 重量 | 价值 |
|---|---|---|
| 物品 0 | 1 | 15 |
| 物品 1 | 3 | 20 |
| 物品 2 | 4 | 30 |
背包最大容量 bag_weight = 4 |
我们的目标就是从这些物品中选择合适的组合放入背包，让背包内物品的总价值最大。
三、动态规划与滚动数组思路
3.1 二维动态规划思路
动态规划解决 0 - 1 背包问题时，通常会使用二维数组 dp[i][j] 来记录状态。其中，i 表示考虑前 i 个物品，j 表示当前背包的容量，dp[i][j] 则表示在前 i 个物品中任意选择，放入容量为 j 的背包所能获得的最大价值。其状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。
3.2 滚动数组优化思路
仔细观察状态转移方程可以发现，计算 dp[i][j] 时仅仅依赖于 dp[i - 1] 这一行的数据。这就意味着，我们不需要保存整个二维数组，只需要一个一维数组就可以完成计算。这种将二维数组压缩成一维数组的思想就是滚动数组。通过滚动数组，我们可以在不影响时间复杂度的情况下，显著降低空间复杂度。
四、具体分析全过程
4.1 初始化 dp 数组
我们使用一维数组 dp 来记录不同背包容量下能获得的最大价值。由于初始时还没有放入任何物品，所以所有容量下的最大价值都为 0。因此，dp = [0, 0, 0, 0, 0]，其中 dp[j] 表示背包容量为 j 时的最大价值。
4.2 考虑物品 0（重量为 1，价值为 15）
外层循环开始遍历物品，当 i = 0 时，开始更新 dp 数组。内层循环从背包最大容量 bag_weight = 4 开始，到物品 0 的重量 weight[0] = 1 结束，且是从大到小遍历。
4.2.1 当 j = 4
- 不选择物品 0：此时
dp[4]保持初始值 0。 - 选择物品 0：
j - weight[0] = 4 - 1 = 3，dp[3]初始为 0，所以dp[3] + value[0] = 0 + 15 = 15。 - 取两者中的最大值更新
dp[4]，即dp[4] = max(0, 15) = 15。
4.2.2 当 j = 3
- 不选择物品 0：
dp[3]为 0。 - 选择物品 0：
j - weight[0] = 3 - 1 = 2，dp[2]为 0，所以dp[2] + value[0] = 0 + 15 = 15。 - 更新
dp[3] = max(0, 15) = 15。
4.2.3 当 j = 2
同理可得，dp[2] = max(0, dp[1] + value[0]) = max(0, 0 + 15) = 15。
4.2.4 当 j = 1
dp[1] = max(0, dp[0] + value[0]) = max(0, 0 + 15) = 15。
此时，考虑完物品 0 后，dp = [0, 15, 15, 15, 15]，这表示当只有物品 0 可供选择时，在不同背包容量下能获得的最大价值。
4.3 考虑物品 1（重量为 3，价值为 20）
当 i = 1 时，继续更新 dp 数组。
4.3.1 当 j = 4
- 不选择物品 1：此时
dp[4]是上一轮考虑物品 0 后的结果，即 15。 - 选择物品 1：
j - weight[1] = 4 - 3 = 1，dp[1]为 15，所以dp[1] + value[1] = 15 + 20 = 35。 - 更新
dp[4] = max(15, 35) = 35。
4.3.2 当 j = 3
- 不选择物品 1：
dp[3]为 15。 - 选择物品 1：
j - weight[1] = 3 - 3 = 0，dp[0]为 0，所以dp[0] + value[1] = 0 + 20 = 20。 - 更新
dp[3] = max(15, 20) = 20。
因为 j 小于物品 1 的重量 3 时，无法放入物品 1，所以 j = 2 和 j = 1 时，dp 值保持不变。
此时，考虑完物品 1 后，dp = [0, 15, 15, 20, 35]。
4.4 考虑物品 2（重量为 4，价值为 30）
当 i = 2 时，更新 dp 数组。
4.4.1 当 j = 4
- 不选择物品 2：
dp[4]是上一轮考虑物品 1 后的结果，即 35。 - 选择物品 2：
j - weight[2] = 4 - 4 = 0，dp[0]为 0，所以dp[0] + value[2] = 0 + 30 = 30。 - 更新
dp[4] = max(35, 30) = 35。
因为 j 小于物品 2 的重量 4 时，无法放入物品 2，所以 j 从 3 到 1 时，dp 值保持不变。
最终，考虑完所有物品后，dp = [0, 15, 15, 20, 35]。
五、代码实现
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4dp = [0] * (bag_weight + 1)for i in range(len(weight)):for j in range(bag_weight, weight[i] - 1, -1):dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bag_weight])
六、代码解释
6.1 初始化部分
定义了物品的重量、价值和背包的最大容量，并初始化一维 dp 数组，将所有元素初始化为 0。
6.2 双重循环部分
- 外层循环：
for i in range(len(weight))遍历每个物品，i表示当前正在考虑的物品编号。 - 内层循环：
for j in range(bag_weight, weight[i] - 1, -1)从背包最大容量开始递减到当前物品的重量。这样做是为了确保每个物品只被选择一次。 - 状态转移方程：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])用于更新dp数组，在不选择当前物品和选择当前物品两种情况中取最大值。
6.3 输出部分
最终输出 dp[bag_weight]，即背包在最大容量下能装下物品的最大价值。
七、复杂度分析
7.1 时间复杂度
O ( n × m ) O(n \times m) O(n×m)，其中 n n n 是物品的数量， m m m 是背包的容量。因为需要遍历每个物品和每个背包容量。
7.2 空间复杂度
O ( m ) O(m) O(m)，使用一维数组 dp 来记录状态，相比二维数组，空间复杂度得到了优化。
八、总结
通过本文的详细分析，我们深入了解了 0 - 1 背包问题的滚动数组解法。滚动数组的思想通过巧妙地利用状态转移方程的特性，将二维数组压缩成一维数组，在不影响时间复杂度的前提下，显著降低了空间复杂度。希望读者通过本文的学习，能够掌握 0 - 1 背包问题的解决方法，并将其应用到实际问题中。
