写在前
背包问题思维导图
问题描述
若有 N 件物品和一个最多能装重量为 W 的背包，一个物品只有两个属性：重量和价值。第i件物品的重量是weight[i]，得到的价值是value[i] 。假设每件物品只能用一次，将哪些物品装入背包里物品价值总和最大？
注意：0-1 背包问题无法使用贪心算法来求解，也就是说，不能按照先添加性价比最高的物品来达到最优，因为这种方式可能造成背包空间的浪费，从而无法达到最优。
背包问题
基本思路
上述问题是典型的动态规划，这里有两个可变量：重量和价值，我们定义dp[i][j]：前i件物品重量不超过j时背包能达到的最大价值，背包的初始状态是最终目标是dp[N][W]，即前N件物品重量不超过W时背包能达到的最大价值。
设第 i 件物品重量为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：
- 第 i 件物品没添加到背包，最大价值：
dp[i][j] = dp[i - 1][j]。 - 第 i 件物品添加到背包中：
dp[i][j] = dp[i - 1][j - w] + v。
第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
代码实现
// W 为背包总重量 // N 为物品数量 // weights 数组存储 N 个物品的重量 // values 数组存储 N 个物品的价值 public int knapsack(int W, int N, int[] weights, int[] values) { // dp[i][0]和dp[0][j]没有价值已经初始化0 int[][] dp = new int[N + 1][W + 1]; // 从dp[1][1]开始遍历填表 for (int i = 1; i <= N; ++i) { // 第i件物品的重量和价值 int w = weights[i - 1], v = values[i - 1]; for (int j = 1; j <= W; ++j) { if (w > j) { // 超过当前状态能装下的重量j dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]); } } } return dp[N][W]; }
由于dp[i][j]的值只与dp[i-1][0,...,j-1]有关，可以采用动态规划常用的优化方法（滚动数组）对空间进行优化（即去掉dp的第一维）。因此，0-1 背包的状态转移方程为： dp[j] = max(dp[j], dp[j - w] + v)
特别注意：为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向遍历。优化空间复杂度：
ps:滚动数组：即让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。
public int knapsack(int W, int N, int[] weights, int[] values) { int[] dp = new int[W + 1]; for (int i = 1; i <= N; i++) { int w = weights[i - 1], v = values[i - 1]; for (int j = W; j >= 1; --j) { if (j >= w) { dp[j] = Math.max(dp[j], dp[j - w] + v); } } } return dp[W]; }
ps：01背包内循环理解：还原成二维的dp就很好理解，一维的dp是二维dp在空间上进行复用的结果。dp[i]=f(dp[i-num])，等式的右边其实是二维dp上一行的数据，应该是只读的，在被读取前不应该被修改。如果正序的话，靠后的元素在读取前右边的dp有可能被修改了，倒序可以避免读取前被修改的问题。
