做服装要看国外哪些网站好,全网营销案例,承包网站开发,刷粉网站推广免费基础
非竞赛只需要搞懂0-1背包和完全背包
0-1背包基础
0-1背包是完全背包和多重背包的基础 n个物品#xff0c;每个物品一个#xff0c;每个物品有自己的重量和价值#xff0c;#xff0c;一个背包能装m物品#xff0c;问最多装多少物品。 暴力解法#xff0c;n个物品…基础
非竞赛只需要搞懂0-1背包和完全背包
0-1背包基础
0-1背包是完全背包和多重背包的基础 n个物品每个物品一个每个物品有自己的重量和价值一个背包能装m物品问最多装多少物品。 暴力解法n个物品2^n
dp数组
可以二维也可以优化成一维
二维
dp[i][j]: 0-i的0物品任选一个放到背包j中价值总和最大是多少。
递推公式
dp[i][j]
不放物品i,物品是 i 背包为j最大价值 dp[i-1][j]:不放物品i的最大价值。
放物品i: 物品为i-1{代表从0到i-1中选物品所以物品i已经被放到背包} dp[i-1]dp[j-weight[i]value[i] {i-1代表0到i个物品去掉i, j-weight[i]{代表物品i放入背包剩下的重量为这个} value[i] 物品的价值 dp[i-1][j-weight[i]]代表放入物品i剩下物品的最大价值 两者相加就是当前背包的最大价值。
物品只有放与不放所以递推公式: dp[i][j] Math.max(dp[i-1][j],Math.max(dp[i-1][j-weight[i]value[i]))
初始化 dp[i][j]由上面{dp[i-1][j]}推除或者左上角推出
还是初始化第一列和第一行
背包容量为0的时候什么也不能放了物品0到i都是初始化为0 第一行这个要初始化的时候要看物品0的重量如果为3
那么3 4这两个要初始化成value[0]
也就是weight[0]到i初始化成value[0]
遍历顺序
先遍历哪个都可以因为从左上和上遍历这两个都可以通过递推公式遍历完 代码
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){// 创建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);}}
}
0-1背包-一维数组
压缩原理 因为每一层都是由上一层得到的所以可以先拷贝到通过滚动数组的形式实现原地修改
dp数组含义
dp[j] : 容量为j时背包最大价值为dp[j]
递推公式
不放物品i因为这个数组是上一层拷贝下来的上一层比如物品1那么这一层是物品2直接拷贝下来是不包含物品2的
所以不妨物品i 容量为j时背包的最大价值就是dp[j] {也就是抛去物品i的最大价值}
放物品i时 容量肯定要编程j-weight[j]的现在放物品i当前逻辑就要加上i的价值value[i] {{{其实从最开始初始化后面价值的总和都是加这个value[i]得到的 所以最大价值时dp[j-weight[i]]
所以递推公式为 dp[j] Math.max(dp[j],dp[j-weight]value[i]){物理上就是数组当前位置和左面-weight位置}
初始化
容量为0 那么价值肯定0
所以初始化dp[0]0;
非0 的话会被覆盖默认为0就可
遍历顺序
现在数组是上一层的结果想要倒叙遍历得到才是正常的计算
代码 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] );}} 416. 分割等和子集
416. 分割等和子集 - 力扣LeetCode
class Solution {public boolean canPartition(int[] nums) {if(nums null || nums.length 0) return false;int sum 0;for(int num : nums) {sum num;}if(sum%2!0) return false;int target sum/2;//dp数组 含义容量为j时最大价值为dp[j]int [] dp new int[target1];//初始化//默认为0即可//遍历顺序//先遍历物品for(int i 0;inums.length;i){for(int j target;jnums[i];j--){//递推公式dp[j] Math.max(dp[j],dp[j-nums[i]]nums[i]);}}return dp[target] target;}}
