辽宁省营商环境建设局网站,做网站优势,数字营销是干啥的,市场推广方案文章目录 01背包问题#xff0c;你该了解这些#xff01;01背包问题#xff0c;你该了解这些#xff01; 滚动数组416. 分割等和子集 01背包问题#xff0c;你该了解这些#xff01;
题目链接#xff1a;代码随想录 二维数组解决0-1背包问题 解题思路#xff1a; 1.dp… 文章目录 01背包问题你该了解这些01背包问题你该了解这些 滚动数组416. 分割等和子集 01背包问题你该了解这些
题目链接代码随想录 二维数组解决0-1背包问题 解题思路 1.dp[i]|[j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 2.确定递推公式不放物品i放物品i dp[i]|[j] max(dp[i - 1]|[j], dp[i - 1]|[j - weight[i]] value[i]); 3.初始化当前处理的结果都是由左上角推出来的所以只用初始化左上和即可即第一行和第一列 4.确定遍历顺序本题无论是先遍历背包还是先遍历物品都可以 图像理解
public class BagProblem {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){//1.创建dp数组//dp[i][j] 表示从0-i个物品中挑选物品放入容量为j的背包中所取得的最大价值int length weight.length;int[][] dp new int[length][bagSize 1];//2.初始化数据只初始化第一行第一列默认初始化为0for (int i weight[0]; i dp.length; i) {//i为物品0的重量dp[0][i] value[0];}//3.遍历dp数组for (int i 1; i weight.length; i) {for (int j 1; j bagSize 1; 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]);}}}for (int i 0; i length; i) {for (int j 0; j bagSize; j) {System.out.print(dp[i][j] \t);}System.out.println(\n);}}
}01背包问题你该了解这些 滚动数组
题目链接代码随想录 一维数组解0-1背包问题 每次放入一个物品之后求得的dp数组就是能放下一个物品的容量的最大价值 因此不用太考虑放入一个物品后前后容量关系就考虑一个个将物品完全放入背包即可 解题思路 1.dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j] 2.dp[j] max(dp[j], dp[j - weight[i]] value[i]); 3.dp数组初始化的时候都初始为0。这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了 4.先遍历放入物品再遍历不同容量的背包从后向前遍历 图像理解 开始向背包里放的时候
public class BagProblemOneArray{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] );// }int goodsLength weight.length;//背包的个数int[] dp new int[bagWeight 1];//dp数组for (int i 0; i goodsLength; i) {for (int j bagWeight; j weight[i]; j--) {dp[j] Math.max(dp[j],dp[j - weight[i]] value[i]);}}for (int i 0; i bagWeight; i) {System.out.print(dp[i] );}}
}416. 分割等和子集
题目链接代码随想录 本题因为元素只能用一次因此是0-1背包问题 整体思路找到元素价值量能恰好装进符合价值sum/2的容量的背包 本题每个商品价值量 重量 解题思路 dp[j] 表示 容量为j的背包所背的物品价值最大可以为dp[j]。 那么如果背包容量为target dp[target]就是装满 背包之后的重量所以 当 dp[target] target 的时候背包就装满了递推公式背包里放入数值那么物品i的重量是nums[i]其价值也是nums[i]。所以递推公式dp[j] max(dp[j], dp[j - nums[i]] nums[i]);初始化dp数组都初始化为0从后向前 图像理解:
public boolean canPartition(int[] nums) {//dp数组// 总和不会大于20000背包最大只需要其中一半所以10001大小就可以了 int[] dp new int[10001];int sum 0;//计算总和for (int i 0; i nums.length; i) {sum nums[i];}if(sum % 2 1){return false;}//为奇数分成两个集合必不成立int target sum / 2;//0-1背包for (int i 0; i nums.length; i) {for (int j target; j nums[i];j--) {//j从target开始因为背包目标重量为即最后求解的结果dp[j] Math.max(dp[j],dp[j - nums[i] nums[i]]);}}if(dp[target] target){return true;}return false;
}
