【动态规划】详解 0-1背包问题

文章目录

1. 问题引入
2. 从 dfs 到动态规划
3. 动态规划过程分析
4. 二维 dp 的遍历顺序
5. 从二维数组到一维数组
6. 一维数组的遍历次序
7. 背包的遍历顺序
8. 代码总结
9. 总结

1. 问题引入

0-1 背包是比较经典的动态规划问题，这里以代码随想录里面的例子来介绍下。总的来说就是：有 n 个物品和一个重量为 w 的背包，这 n 个物品中第 i 个物品的重量为 w[i]，价值为 v[i]，那么这个背包能装下的物品最大价值是多少，注意一个物品只能选一次。
在这里插入图片描述

2. 从 dfs 到动态规划

我们来把问题具体化，假设现在有一个重量为 4 的背包，有 3 个物品，物品的重量和价值如下：

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

那么现在将物品装入背包，能装入的物品的最大价值是多少呢？要想解决动态规划问题，我们总得从 dfs 入手，那就先从 dfs 讲讲。

public class Main {public static void main(String[] args) {Main main = new Main();main.findMax(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4);main.findMax(new int[]{1, 3}, new int[]{15, 20}, 3);}public void findMax(int[] weight, int[] prices, int max){int res = dfs(weight, prices, max, weight.length - 1);System.out.println("最大价值是: " + res);}private int dfs(int[] weight, int[] prices, int max, int i) {if(i < 0){// 遍历到尾部了return 0;}// 不选当前的价值int noPick = dfs(weight, prices, max, i - 1);// 如果剩余重量大于 weight[i] 才可选return max >= weight[i] ? Math.max(prices[i] + dfs(weight, prices, max - weight[i], i - 1), noPick) : noPick;}
}

dfs 的遍历逻辑很简单，就是从后往前遍历，然后对于当前物品，可以选或者不选，但是有条件，如果选的话剩余的容量必须要大于 weight[i]，否则就不能选，因为剩余重量装不下当前物品。

但是我们知道，这个方法是会超时的，如果数组长度比较大，因为里面有不少重复计算，既然这样我们就加上记忆化搜索。

public class Main {public static void main(String[] args) {Main main = new Main();main.findMax(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4);main.findMax(new int[]{1, 5}, new int[]{15, 20}, 3);}public void findMax(int[] weight, int[] prices, int max){// memo[i][j] 的意思是从 [0...i] 中将物品放到重量为 j 的背包，最大值是多少int[][] memo = new int[weight.length][max + 1];for (int[] arr : memo) {Arrays.fill(arr, -1);}int res = dfs(weight, prices, max, weight.length - 1, memo);System.out.println("最大价值是: " + res);}private int dfs(int[] weight, int[] prices, int max, int i, int[][] memo) {if(i < 0){// 遍历到尾部了return 0;}if(memo[i][max] != -1){return memo[i][max];}// 不选当前的价值int noPick = dfs(weight, prices, max, i - 1, memo);return memo[i][max] = (max >= weight[i] ? Math.max(prices[i] + dfs(weight, prices, max - weight[i], i - 1, memo), noPick) : noPick);}
}

好了，在记忆化搜索的基础上，我们再来改造成动态规划，首先我们看上面的 dfs 逻辑，当前 i 的结果是基于 i - 1 得来的，也就是说我们可以得到下面的递推公式：

$d p [i] [j] = M a t h . ma x (d p [i - 1] [j], p r i ces [i] + d p [i - 1] [j - w e i g h t [i]])$
上面的意思是如果不选当前下标 i 的物品，那么就继续往前找
如果选当前下标 i 的物品，那么价值就是 prices[i]，接着 j 要减去物品 i 的价值

好了，递推公式有了，那么如何初始化呢？我们知道 dp[i][j] 的意思是：在下标 [0…i] 中选择物品装入重量为 j 的背包，能装入的最大值是多少！

当 i = 0 的时候，dp[0][j] 表示下标 0 物品装入重量为 j 的背包，最大值是多少。
当 j = 0 的时候，dp[i][0] 表示下标 [0…i] 的物品装入重量为 0 的背包，最大值是多少，自然是 0 了。

所以初始化如下：

int[][] dp = new int[weight.length][max + 1];
for(int j = 0; j <= max; j++){if(j > weight[0]){dp[0][j] = prices[i];}
}

下面再结合记忆化搜索的代码，就能写出来下面的动态规划代码。

public int findMaxD(int[] weight, int[] prices, int max){int[][] dp = new int[weight.length][max + 1];for(int j = 0; j <= max; j++){if(j >= weight[0]){dp[0][j] = prices[0];}}// 遍历物品for(int i = 1; i < weight.length; i++){// 遍历背包for(int j = 0; j <= max; j++){if(j < weight[i]){dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], prices[i] + dp[i - 1][j - weight[i]]);}}}return dp[weight.length - 1][max];
}

3. 动态规划过程分析

上面我们写出了动态规划的代码，但是不知道大家有没有疑问，就是这个物品和背包的遍历是有顺序的吗？注意我这里指的是二维的 dp 数组，现在我们讨论都是在二维 dp 的基础上去讨论，后面会逐步演变成一维 dp。

首先就是递推公式

$d p [i] [j] = M a t h . ma x (d p [i - 1] [j], p r i ces [i] + d p [i - 1] [j - w e i g h t [i]])$ ，根据这个递推公式，

通过这个递推公式，我们能发现 dp[i][j] 其实依赖当前格子的上边和左上的格子。
在这里插入图片描述
那么从这个角度，我们再来看动态规划的初始化，你就知道为什么要初始化 i = 0 和 j = 0 的格子值了（j = 0 不需要初始化，因为都是 0）。

初始化完第一行之后，再从第二行开始通过递推公式填充格子，最终填充好的结果如下所示：
在这里插入图片描述
我用下标（1，3）举个例子，当 i = 1，j = 3 的时候，如果不选当前物品，那么就是 dp[0][3]，如果选当前物品，那么就是 dp[1 - 1][3 - 3] + 20 = 20，两者取最大值就是 20，遍历顺序是从左到右，从上到下。

4. 二维 dp 的遍历顺序

好了，上面我们解析了 dp 数组的填充过程，那么如果是先遍历物品，再遍历背包，填充的过程就是 从左到右，从上到下。那么如果是先遍历背包，再遍历物品呢？

还是回到 dp 图，如果先遍历背包，再遍历物品，其实就是从从上到下，从左到右。
在这里插入图片描述
那么我们想一下，如果是这种遍历顺序，在遍历到 dp[1][3] 的时候，dp[0][3] 和 dp[0][0] 初始化了吗，换句话说，当遍历到第 i 行的时候，第 i - 1 行初始化了吗？

从遍历过程就能看到，其实是初始化了的，所以我们先遍历背包，再遍历物品也是没问题的。如何遍历，遍历顺序是什么就取决于当遍历到（i，j）的时候，需要依赖的格子有没有初始化。

public int findMaxD(int[] weight, int[] prices, int max) {int[][] dp = new int[weight.length][max + 1];for (int j = 0; j <= max; j++) {if (j >= weight[0]) {dp[0][j] = prices[0];}}// 遍历背包for (int j = 0; j <= max; j++) {// 遍历物品for (int i = 1; i < weight.length; i++) {if (j < weight[i]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], prices[i] + dp[i - 1][j - weight[i]]);}}}return dp[weight.length - 1][max];
}

那么我再问一句，遍历背包能倒叙遍历吗？其实从 dp 数组的依赖就能看出，可以！！！ 因为第 i 行的数据只和第 i - 1 行有关，和本行无关，而我们知道 dp 数组在处理到第 i 行的时候 i - 1就已经处理好了，所以爱怎么遍历就怎么遍历。

5. 从二维数组到一维数组

上面我们使用二维数组对 dp 进行填充了，但是大家有没有注意到，第 i 行的结果只依赖第 i - 1 行，所以我们完全可以只使用一维数组，把 i 省略掉。相当于把 i 的结果粘贴到 i - 1行的位置，所以 dp[i] 就表示重量为 i 的容量能装入的最大物品价值是多少 ，大体过程如下：

初始化 dp[0]
根据 dp[0] 初始化 dp[1]
…

初始化 dp[0] 的时候，重量为 0 的背包肯定是放不下任何物品的，所以不需要初始化，下面看遍历逻辑。

public int findMax(int[] weight, int[] prices, int max){int[] dp = new int[max + 1];// 遍历物品for(int i = 0; i < weight.length; i++){// 遍历背包for(int j = max; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]);}}return dp[max];
}

注意下 dp 公式为：

$d p [j] = M a t h . ma x (d p [j], d p [j - w e i g h t [i]] + p r i ces [i])$

大家可能好奇为什么可以直接和 dp[j] 做比较，我把二维数组的 dp 粘贴过来。
在这里插入图片描述
dp 数组初始化为 0，当 i = 0 的时候，其实就是在初始化第一行 [0，15，15，15，15]。当 i = 1 的时候，记住此时 dp 记录的是 i = 0 的结果，那么 dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]) 其实就是在根据 i = 0 来更新 i = 1 的数据，一直这样遍历下去，遍历到最后就是我们要的结果了。

6. 一维数组的遍历次序

上面一维数组的遍历次序是先遍历物品，再遍历背包，那么可以先遍历背包，再遍历物品吗？也就是下面的写法。

// 遍历背包
for (int j = max; j >= 0; j--) {// 遍历物品for (int i = 0; i < weight.length; i++) {if (j >= weight[i]) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]);}}
}

让我们看下这个过程，当 j = 4 的时候，遍历所有物品，求 dp[j] 能放下的物品的最大价值，为什么我说求 dp[j] 的最大价值，因为是倒叙遍历，同时又是 j 在外层一直往前遍历，所以 dp[j - weight[i]] 你就当成 0 就好了，相当于 dp[j] = Math.max(dp[j], prices[i])。

所以最终求出来的结果就是当前这个重量下能放下的物品的最大价值（单个）。

所以这里的遍历顺序就得是：先遍历物品，再遍历背包。

7. 背包的遍历顺序

public int findMax(int[] weight, int[] prices, int max){int[] dp = new int[max + 1];// 遍历物品for(int i = 0; i < weight.length; i++){// 遍历背包for(int j = max; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]);}}return dp[max];
}

继续回到遍历逻辑，注意到背包是从后往前遍历的，那么为什么不能从前往后遍历呢？

我们仔细看下 dp 的意义，由于从二维降到一维，我们在遍历的时候是不断用新获取的 dp[j] 覆盖原来的 dp[j]，还是从二维数组的 dp 看下。
在这里插入图片描述
我上面说的意思相当于说，现在一维 dp 的数组是物品 0 所在的这行数据 [0，15，15，15，15]。当 i = 1 的时候，求出来的 20 会立马覆盖回数组，这时候数组是 [0，15，15，20，15]，j = 3，继续往前遍历。

而如果缓存背包从前往后遍历，结果会是怎么样呢？我把物品的重量和价格粘贴过来。

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

这次我们就看 i = 0 的遍历结果，初始化数组全是 0。
在这里插入图片描述

dp[0] = 0
dp[1] = Math.max(dp[1], dp[1-weight[0]] + prices[0]) = 15
dp[2] = Math.max(dp[2], dp[2-weight[0]] + prices[0]) = 30
dp[3] = Math.max(dp[3], dp[3-weight[0]] + prices[0]) = 45
…

最终结果就变成了：
在这里插入图片描述
其实出现这种情况，就是完全背包的做法了，也就是一个物品被选择了多个。

那么为什么会出现这种情况呢？其实我们还是可以从一维 dp 入手。

$d p [j] = M a t h . ma x (d p [j], d p [j - w e i g h t [i]] + p r i ces [i])$

上面是一维的公式，假设现在数字组初始化为 0，那么在初始化 i = 0 的时候假设初始化了 dp[1] = 15，大家记住，这里的 dp 是实时覆盖的，所以这时候的状态如下：
在这里插入图片描述
这时候 dp[0] 和 dp[1] 都计算过了并且覆盖会原数组下标，而 dp[2]、dp[3]、dp[4] 还保留初始化的状态，啥意思呢，换成 i - 1 和 i，意思就是这时候 dp[0] 和 dp[1] 是 i = 1 计算出来的，而 dp[2]、dp[3]、dp[4] 则还是 dp[i-1] 的状态。

我们接下来继续看 dp[2]，我们知道 dp[2] = Math.max(dp[2], dp[1] + 15) = 30，意思就是在计算 dp[2] 的时候使用到了 dp[1]，而这个 dp[1] 已经被覆盖过了，意思就是这个 dp[1] 不是 i - 1 的值了，而是 i 的值，所以就造成了多次选择。

在二维数组中计算 dp[i] 的时候是使用 dp[i-1] 的值，因为不会被覆盖，所以遍历顺序就无所谓。但是一维数组就不一样的，因为会实时覆盖，所以只能从后往前遍历，否则就会用前面已经计算过的值来计算当前下标的值了。

8. 代码总结

好了，到这里我们就解析完0-1背包了，分为二维和一维，其实说了这么多，大家只需要记住两个版本就行了。

public int findMaxD(int[] weight, int[] prices, int max){int[][] dp = new int[weight.length][max + 1];for(int j = 0; j <= max; j++){if(j >= weight[0]){dp[0][j] = prices[0];}}// 遍历物品for(int i = 1; i < weight.length; i++){// 遍历背包for(int j = 0; j <= max; j++){if(j < weight[i]){dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], prices[i] + dp[i - 1][j - weight[i]]);}}}return dp[weight.length - 1][max];
}

一维的遍历如下：

public int findMax(int[] weight, int[] prices, int max){int[] dp = new int[max + 1];// 遍历物品for(int i = 0; i < weight.length; i++){// 遍历背包for(int j = max; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]);}}return dp[max];
}