如何建设视频网站,刚刚封城最新消息2021,网站服务器维护需要多久,企业建设网站的母的01背包的问题描述#xff1a;#xff08;内容参考代码随想录#xff09;有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。问题示例#…01背包的问题描述内容参考代码随想录有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。问题示例背包最大重量为4。重量价值物品0115物品1320物品2430解法一暴力求解每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是o(2^n)这里的n表示物品数量。所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化解法二二维dp数组01背包1.确定dp数组以及下标的含义dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。2.确定递推公式不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以被背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);3.dp数组初始化如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。dp[0][j]即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。那么很明显当 j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。当j weight[0]时dp[0][j] 应该是value[0]因为背包容量放足够放编号0物品。从递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了那么 其他下标初始为什么数值都可以因为都会被覆盖。4.确定遍历顺序虽然两个for循环遍历的次序不同不管是先遍历背包还是先遍历物品dp[i][j]所需要的数据就是左上角根本是不影响结果的。public static void main(String[] args) {int[] weight {1,3,4};int[] value {15,20,30};int bagSize 4;testWeightBagProblem(weight,value,bagSize);}/*** 动态规划获得结果* param weight 物品的重量* param value 物品的价值* param bagSize 背包的容量*/public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 创建dp数组int goods weight.length; // 获取物品的数量int[][] dp new int[goods][bagSize 1];// 初始化dp数组// 创建数组后其中默认的值就是0for (int j weight[0]; j bagSize; j) {dp[0][j] value[0];}// 填充dp数组for (int i 1; i weight.length; i) {for (int j 1; j bagSize; j) {if (j weight[i]) {/*** 当前背包的容量都没有当前物品i大的时候是不放物品i的* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值*/dp[i][j] dp[i-1][j];} else {/*** 当前背包的容量可以放下物品i* 那么此时分两种情况* 1、不放物品i* 2、放物品i* 比较这两种情况下哪种背包中物品的最大价值最大*/dp[i][j] Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] value[i]);}}}// 打印dp数组for (int i 0; i goods; i) {for (int j 0; j bagSize; j) {System.out.print(dp[i][j] \t);}System.out.println(\n);}}解法三一维dp数组01背包1.确定dp数组的定义在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。2.一维dp数组的递推公式dp[j]有两个选择一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]即不放物品i一个是取dp[j - weight[i]] value[i]即放物品i指定是取最大的毕竟是求最大价值。3.一维dp数组如何初始化dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]那么dp[0]就应该是0因为背包容量为0所背的物品的最大价值就是0。根据递归公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);所以在初始化的时候不能初始化较大的值因为dp[j]是求最大值得出的不然会影响结果初始为非负数中最小的就行初始化为0就合适。4.一维dp数组遍历顺序二维dp遍历的时候背包容量是从小到大而一维dp遍历的时候背包是从大到小。倒序遍历是为了保证物品i只被放入一次因为一维数组的结果要依赖前一次的结果所以如果正序遍历那么就会造成前面的结果重复计算。所以从后往前循环每次取得状态不会和之前取得状态重合这样每种物品就只取一次了。为什么二维dp数组历的时候不用倒序呢因为对于二维dpdp[i][j]都是通过上一层即dp[i - 1][j]计算而来本层的dp[i][j]并不会被覆盖两个嵌套for循环的顺序一定是先遍历物品嵌套遍历背包容量不能颠倒。 public static void main(String[] args) {int[] weight {1, 3, 4};int[] value {15, 20, 30};int bagWight 4;testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen weight.length;//定义dp数组dp[j]表示背包容量为j时能获得的最大价值int[] dp new int[bagWeight 1];//遍历顺序先遍历物品再遍历背包容量for (int i 0; i wLen; i){for (int j bagWeight; j weight[i]; j--){dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}//打印dp数组for (int j 0; j bagWeight; j){System.out.print(dp[j] );}}小结01背包问题用二维数组dp[i][j]和一维数组dp[i]来求解两者有很大区别。在dp数组的含义dp数组的初始化以及for循环嵌套顺序以及遍历顺序都是不同的。完全背包问题01背包和完全背包的区别在于01背包的物品只能使用一次而完全背包的物品可以无限次使用所以在遍历顺序上是有区别的。01背包问题为了能让每个物品只使用一次所以是倒序遍历背包而完全背包就改为正序遍历了。很简单的理解啊因为正序遍历后一个背包状态要依赖前一个背包的状态所以一个物品可以被加了多次而倒序遍历因为前面的背包状态是初始值所以后一个背包加了前面的背包状态也是无效的。同样跟01背包的dp二维数组一样两层for循环也是可以颠倒的。//先遍历物品再遍历背包
private static void testCompletePack(){int[] weight {1, 3, 4};int[] value {15, 20, 30};int bagWeight 4;int[] dp new int[bagWeight 1];for (int i 0; i weight.length; i){ // 遍历物品for (int j weight[i]; j bagWeight; j){ // 遍历背包容量dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}for (int maxValue : dp){System.out.println(maxValue );}
}//先遍历背包再遍历物品
private static void testCompletePackAnotherWay(){int[] weight {1, 3, 4};int[] value {15, 20, 30};int bagWeight 4;int[] dp new int[bagWeight 1];for (int i 1; i bagWeight; i){ // 遍历背包容量for (int j 0; j weight.length; j){ // 遍历物品if (i - weight[j] 0){dp[i] Math.max(dp[i], dp[i - weight[j]] value[j]);}}}for (int maxValue : dp){System.out.println(maxValue );}
}
