asp装修公司网站,wordpress客户端定制,搜索引擎网站推广可以自己做吗,做智能网站软件下载文章目录 1. 问题引入2. 从 dfs 到动态规划3. 动态规划过程分析4. 二维 dp 的遍历顺序5. 从二维数组到一维数组6. 一维数组的遍历次序7. 背包的遍历顺序8. 代码总结9. 总结 1. 问题引入
0-1 背包是比较经典的动态规划问题#xff0c;这里以代码随想录里面的例子来介绍下。总的… 文章目录 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 个物品物品的重量和价值如下
重量价值物品 0115物品 1320物品 2430
那么现在将物品装入背包能装入的物品的最大价值是多少呢要想解决动态规划问题我们总得从 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 . m a x ( d p [ i − 1 ] [ j ] , p r i c e s [ i ] d p [ i − 1 ] [ j − w e i g h t [ i ] ] ) dp[i][j] Math.max(dp[i-1][j], prices[i] dp[i-1][j-weight[i]]) dp[i][j]Math.max(dp[i−1][j],prices[i]dp[i−1][j−weight[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 . m a x ( d p [ i − 1 ] [ j ] , p r i c e s [ i ] d p [ i − 1 ] [ j − w e i g h t [ i ] ] ) dp[i][j] Math.max(dp[i-1][j], prices[i] dp[i-1][j-weight[i]]) dp[i][j]Math.max(dp[i−1][j],prices[i]dp[i−1][j−weight[i]])根据这个递推公式
通过这个递推公式我们能发现 dp[i][j] 其实依赖当前格子的上边和左上的格子。 那么从这个角度我们再来看动态规划的初始化你就知道为什么要初始化 i 0 和 j 0 的格子值了j 0 不需要初始化因为都是 0。 初始化完第一行之后再从第二行开始通过递推公式填充格子最终填充好的结果如下所示 我用下标 13举个例子当 i 1j 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 行初始化了吗
从遍历过程就能看到其实是初始化了的所以我们先遍历背包再遍历物品也是没问题的。如何遍历遍历顺序是什么就取决于当遍历到ij的时候需要依赖的格子有没有初始化。
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 . m a x ( d p [ j ] , d p [ j − w e i g h t [ i ] ] p r i c e s [ i ] ) dp[j] Math.max(dp[j], dp[j - weight[i]] prices[i]) dp[j]Math.max(dp[j],dp[j−weight[i]]prices[i])
大家可能好奇为什么可以直接和 dp[j] 做比较我把二维数组的 dp 粘贴过来。 dp 数组初始化为 0当 i 0 的时候其实就是在初始化第一行 [015151515]。当 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 所在的这行数据 [015151515]。当 i 1 的时候求出来的 20 会立马覆盖回数组这时候数组是 [015152015]j 3继续往前遍历。
而如果缓存背包从前往后遍历结果会是怎么样呢我把物品的重量和价格粘贴过来。
重量价值物品 0115物品 1320物品 2430
这次我们就看 i 0 的遍历结果初始化数组全是 0。
dp[0] 0dp[1] Math.max(dp[1], dp[1-weight[0]] prices[0]) 15dp[2] Math.max(dp[2], dp[2-weight[0]] prices[0]) 30dp[3] Math.max(dp[3], dp[3-weight[0]] prices[0]) 45…
最终结果就变成了 其实出现这种情况就是完全背包的做法了也就是一个物品被选择了多个。
那么为什么会出现这种情况呢其实我们还是可以从一维 dp 入手。 d p [ j ] M a t h . m a x ( d p [ j ] , d p [ j − w e i g h t [ i ] ] p r i c e s [ i ] ) dp[j] Math.max(dp[j], dp[j - weight[i]] prices[i]) dp[j]Math.max(dp[j],dp[j−weight[i]]prices[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];
}9. 总结
我们总结下二维数组和一维数组的遍历顺序 二维数组 背包和物品的遍历顺序可以颠倒遍历背包的时候可以正序和倒叙遍历 一维数组 先遍历物品再遍历背包遍历背包需要倒叙遍历 如有错误欢迎指出
