大岭山镇网站建设公司,网站安全建设申请,网络营销的培训课程,dede网站如何换源码所用代码 java 01背包理论
背包最大重量为#xff1a;4
重量价值物品0115物品1320物品2430
暴力#xff1a;O(2^n)
动态规划#xff1a;
1、二维dp数组 dp[i] [j] dp数组含义#xff1a;[0, i]物品#xff0c;任取放进容量为j的背包里的最大价值 递推公式#xff1a… 所用代码 java 01背包理论
背包最大重量为4
重量价值物品0115物品1320物品2430
暴力O(2^n)
动态规划
1、二维dp数组 dp[i] [j] dp数组含义[0, i]物品任取放进容量为j的背包里的最大价值 递推公式 不放物品i dp[i-1] [j]放物品idp[i-1] [j - weight[i]] value[i] dp[i] [j] Math.max(dp[i-1] [j], dp[i-1] [j - weight[i]] value[i] 初始化 dp[i] [j] i物品 j背包容量(0 1 2 3 4 )
01234物品0015151515物品10n 由上和左上推出物品20
遍历顺序对于二维数组的01背包先背包后物品先物品后背包都可以打印dp数组
具体代码
public class 背包01 {public static void main(String[] args) {int[] weight {1,3,4};int[] value {15,20,30};int bagSize 4;bagProblem01(weight,value,bagSize);}public static void bagProblem01(int[] weight, int[] value, int bagSize){int goods weight.length; // 物品数量int[][] dp new int[goods][bagSize 1];// 初始化 - 只有一个物品的时候不管背包多大加载都是该物品的价值for (int j 0; j bagSize; j) {dp[0][j] value[0];}// 背包i在背包容量为0的时候最大价值为0for (int i 0; i goods; i) {dp[i][0] 0;}// 先遍历背包再遍历物品for (int i 1; i goods; i) {for (int j 1; j bagSize; j) {if (j weight[i]){// 当背包容量没有当我物品那么大时就是放不下物品最大的重量为i-1时最大重量dp[i][j] dp[i-1][j];}else {// 可以放下物品时比较放物品后的价值和没放物品价值谁大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();}}
}
打印结果
0 15 15 15 15
0 15 15 20 35
0 15 15 20 352、一维dp数组dp[j] - 滚动数组
dp[j]容量为j的背包最大价值为dp[j] i为物品递推公式dp[j] max(dp[j], dp[j-weight[i]] value[i])初始化dp[0] 0 其他非负里面的最小值如0。遍历顺序 先遍历物品再遍历背包倒序遍历保证每个物品只被添加了一次。 打印dp数组
public static void bagProblem1(int[] weight, int[] value, int bagSize){int goods weight.length; // 物品数量int[] dp new int[bagSize 1];// 初始化Arrays.fill(dp, 0);// 先遍历背包再遍历物品for (int i 0; i goods; i) {// j weight[i] 保证从右向左遍历的时候dp[j-weight[i]]不会越界for (int j bagSize; j weight[i]; j--){dp[j] Math.max(dp[j-1], dp[j-weight[i]] value[i]);}}// 打印for (int MaxValue : dp) {System.out.print(MaxValue \t);}
}分割等和子集 LeetCode 416
题目链接分割等和子集 LeetCode 416 - 中等
思路
试了滑动窗口不行。滑动窗口适合连续的数。 应该抽象为一个背包背包的容量为数组和的一半只要装下一半另一半肯定可以。
dp[j] 容量为j的背包能装下的最大价值为dp[j]递推公式dp[j] max(dp[j], dp[j-nums[i]] nums[i]) 重量和价值是相同的初始化dp[0] 0背包不可能是负数需初始成非负整数的最大值 0遍历方向从右到左打印dp数组
一维数组
class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int num : nums) {sum num;}if (sum % 2 1) return false;// target 相当于背包的容量int target sum / 2;// dp数组初始为0int[] dp new int[target 1];// 物品for (int i 0; i nums.length; i) {for (int j target; j nums[i]; j--){dp[j] Math.max(dp[j], dp[j-nums[i]] nums[i]);}}// 看一下最后一个数是不是targetreturn dp[target] target;}
}二维数组
dp[i] [j] 前i个数其总价值不超过j的最大价值为dp[i] [j] j代表的是背包重量递推公式dp[i] [j] Math.max(dp[i-1] [j], dp[i-1] [j - nums[i]] nums[i]);初始化小于num[0]的不能装初始化为0其余为nums[0]
class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int num : nums) {sum num;}if (sum % 2 1) return false;// target 相当于背包的容量int target sum / 2;int[][] dp new int[nums.length][target 1];// 初始化只有一个物品时的重量for (int j 0; j target; j) {dp[0][j] j nums[0] ? nums[0] : 0;}// 物品数量for (int i 1; i nums.length; i) {// 背包容量背包容量0默认不能装for (int j 1; j target; j) {// 不能装下物品最大值就是前一个值if (j nums[i]){dp[i][j] dp[i-1][j];}else {dp[i][j] Math.max(dp[i-1][j], dp[i-1][j - nums[i]] nums[i]);}
// System.out.print(dpdp[i][j] \t);}
// System.out.println();}return dp[nums.length-1][target] target;}
}总结
本题主要是分析只要把该题分析出来是背包问题的话照着这个思路就非常的简单。
第二点就是二维数组在初始化的适合需要注意背包重量小于nums[0]的数是没法装的需初始化为0。
另外还有一种思路
dp[i] [j] 从[0, i]区间中挑选一些正整数每个数只能用一次这些数的和恰好为 j递推公式dp[i] [j] dp[i - 1] [j] || dp[i - 1] [j - nums[i]]初始化在num[0] target 的情况下第一个数只能让容积为自己的背包填满dp[0] [num[0]] true
class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int num : nums) sumnum;if (sum % 2 1) return false;// target 相当于背包的容量int target sum / 2;boolean[][] dp new boolean[nums.length][target 1];// 初始化填满第一行的dp[0][nums[0]] 只有nums[0]本身if (nums[0] target) dp[0][nums[0]] true;// System.out.print(dp[0] Arrays.toString(dp[0]));
// System.out.println();// 外层遍历物品数量for (int i 1; i nums.length; i) {// 内层遍历背包for (int j 0; j target; j) {// 先取上一次的结果后面进行修正dp[i][j] dp[i-1][j];// 如果某个物品的重量恰好等于背包重量则满足条件// 所以这一列的值都为trueif (nums[i] j){dp[i][j] true;
// System.out.print(***dp[i][j] \t\t);continue;}// 如果该物品小于背包的重量就判断能否加入新的物品// dp[i-1][j]表示不放入背包如果前面有满足条件后面就一定可以满足// dp[i-1][j-nums[i]]表示放入背包放入后判断放入背包的区间有没有满足条件的就是左上if (nums[i] j){dp[i][j] dp[i-1][j] || dp[i-1][j-nums[i]];}
// System.out.print(dpdp[i][j] \t\t);}
// System.out.println();}return dp[nums.length-1][target];}
}
