玉溪住房和城乡建设局网站,洛阳建设银行官方网站,个人网站优秀,百度一下点击搜索算法训练营 day45 动态规划 0-1背包理论 分割等和子集
0-1背包理论 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。 在下面的讲解中…算法训练营 day45 动态规划 0-1背包理论 分割等和子集
0-1背包理论 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 在下面的讲解中我举一个例子
背包最大重量为4。
物品为
重量价值物品0115物品1320物品2430
二维dp数组
确定dp数组以及下标的含义
对于背包问题有一种写法 是使用二维数组即dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
看下面这个图 确定递推公式
再回顾一下dp[i][j]的含义从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]
不放物品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]);
dp数组如何初始化
关于初始化一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0
在看其他情况。
状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出i 是由 i-1 推导出来那么i为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数组初始化情况如图所示 确定遍历顺序
在如下图中可以看出有两个遍历的维度
那么问题来了先遍历 物品还是先遍历背包重量呢
其实都可以 但是先遍历物品更好理解。
要理解递归的本质和递推的方向。
dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向包括正上方向那么先遍历物品再遍历背包的过程如图所示 再来看看先遍历背包再遍历物品呢如图
大家可以看出虽然两个for循环遍历的次序不同但是dp[i][j]所需要的数据就是左上角根本不影响dp[i][j]公式的推导
举例推导dp数组
来看一下对应的dp数组的数值如图 class Main {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数组
对于背包问题其实状态都是可以压缩的。
在使用二维数组的时候递推公式dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上表达式完全可以是dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上不如只用一个一维数组了只用dp[j]一维数组也可以理解是一个滚动数组。
确定dp数组的定义
在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。
一维dp数组的递推公式
dp[j]可以通过dp[j - weight[i]]推导出来dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
dp[j - weight[i]] value[i] 表示 容量为 j - 物品i重量 的背包 物品i的价值。也就是容量为j的背包放入物品i了之后的价值即dp[j]
此时dp[j]有两个选择一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]即不放物品i一个是取dp[j - weight[i]] value[i]即放物品i指定是取最大的毕竟是求最大价值
一维dp数组如何初始化
dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]那么dp[0]就应该是0因为背包容量为0所背的物品的最大价值就是0。
看一下递归公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);
dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
一维dp数组遍历顺序
二维dp遍历的时候背包容量是从小到大而一维dp遍历的时候背包是从大到小。
倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品0就会被重复加入多次
举例推导dp数组
一维dp分别用物品0物品1物品2 来遍历背包最终得到结果如下 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. 分割等和子集 - 力扣LeetCode
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
只有确定了如下四点才能把01背包问题套到本题上来。
背包的体积为sum / 2背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。
以上分析完我们就可以套用01背包来解决这个问题了。 确定dp数组以及下标的含义 01背包中dp[j] 表示 容量为j的背包所背的物品价值最大可以为dp[j]。 本题中每一个元素的数值既是重量也是价值。 套到本题dp[j]表示 背包总容量所能装的总重量是j放进物品后背的最大重量为dp[j]。 那么如果背包容量为target dp[target]就是装满 背包之后的重量所以 当 dp[target] target 的时候背包就装满了。 确定递推公式 01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]); 本题相当于背包里放入数值那么物品i的重量是nums[i]其价值也是nums[i]。 所以递推公式dp[j] max(dp[j], dp[j - nums[i]] nums[i]); dp数组如何初始化 在01背包一维dp如何初始化已经讲过 从dp[j]的定义来看首先dp[0]一定是0。 如果题目给的价值都是正整数那么非0下标都初始化为0就可以了如果题目给的价值有负数那么非0下标就要初始化为负无穷。 这样才能让dp数组在递推的过程中取得最大的价值而不是被初始值覆盖了。 确定遍历顺序 如果使用一维dp数组物品遍历的for循环放在外层遍历背包的for循环放在内层且内层for循环倒序遍历 举例推导dp数组
dp[j]的数值一定是小于等于j的。
如果dp[j] j 说明集合中的子集总和正好可以凑成总和j理解这一点很重要。
用例1输入[1,5,11,5] 为例如图 最后dp[11] 11说明可以将这个数组分割成两个子集使得两个子集的元素和相等。
一维dp数组
class Solution {public static boolean canPartition(int[] nums) {int sum 0;for (int i 0; i nums.length; i) {sum nums[i];}if(sum % 2 ! 0) return false;int target sum / 2;int[] dp new int[target1];for (int i 0; i nums.length; i) {for (int j target;jnums[i];j--) {if (j nums[i]) {dp[j] dp[j];} else {dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}}}return dp[target]target;}
}二维dp数组
class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int i 0; i nums.length; i) {sum nums[i];}if(sum % 2 ! 0) return false;int target sum / 2;int[][] dp new int[nums.length][target1];for (int j nums[0]; j target; j) {dp[0][j] nums[0];}for (int i 1; i nums.length; i) {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]);}}}return dp[nums.length-1][target]target;}
}
文章转载自： http://www.morning.rpgdd.cn.gov.cn.rpgdd.cn http://www.morning.rjynd.cn.gov.cn.rjynd.cn http://www.morning.lywpd.cn.gov.cn.lywpd.cn http://www.morning.lgznc.cn.gov.cn.lgznc.cn http://www.morning.fxjnn.cn.gov.cn.fxjnn.cn http://www.morning.ljcjc.cn.gov.cn.ljcjc.cn http://www.morning.lmcrc.cn.gov.cn.lmcrc.cn http://www.morning.bkkgt.cn.gov.cn.bkkgt.cn http://www.morning.zrdhd.cn.gov.cn.zrdhd.cn http://www.morning.nwnbq.cn.gov.cn.nwnbq.cn http://www.morning.mpflb.cn.gov.cn.mpflb.cn http://www.morning.zsyqg.cn.gov.cn.zsyqg.cn http://www.morning.xrwtk.cn.gov.cn.xrwtk.cn http://www.morning.yhyqg.cn.gov.cn.yhyqg.cn http://www.morning.rzmzm.cn.gov.cn.rzmzm.cn http://www.morning.gqhgl.cn.gov.cn.gqhgl.cn http://www.morning.wbdm.cn.gov.cn.wbdm.cn http://www.morning.bbgn.cn.gov.cn.bbgn.cn http://www.morning.sltfk.cn.gov.cn.sltfk.cn http://www.morning.nwqyq.cn.gov.cn.nwqyq.cn http://www.morning.cwgfq.cn.gov.cn.cwgfq.cn http://www.morning.tbnpn.cn.gov.cn.tbnpn.cn http://www.morning.jmlgk.cn.gov.cn.jmlgk.cn http://www.morning.zpdjh.cn.gov.cn.zpdjh.cn http://www.morning.wqmpd.cn.gov.cn.wqmpd.cn http://www.morning.hmnhp.cn.gov.cn.hmnhp.cn http://www.morning.qymqh.cn.gov.cn.qymqh.cn http://www.morning.trjp.cn.gov.cn.trjp.cn http://www.morning.msfqt.cn.gov.cn.msfqt.cn http://www.morning.qnrpj.cn.gov.cn.qnrpj.cn http://www.morning.clyhq.cn.gov.cn.clyhq.cn http://www.morning.fbhmn.cn.gov.cn.fbhmn.cn http://www.morning.chrbp.cn.gov.cn.chrbp.cn http://www.morning.fcftj.cn.gov.cn.fcftj.cn http://www.morning.zdbfl.cn.gov.cn.zdbfl.cn http://www.morning.jwbfj.cn.gov.cn.jwbfj.cn http://www.morning.xcbnc.cn.gov.cn.xcbnc.cn http://www.morning.pwhjr.cn.gov.cn.pwhjr.cn http://www.morning.ckcjq.cn.gov.cn.ckcjq.cn http://www.morning.gwkwt.cn.gov.cn.gwkwt.cn http://www.morning.khntd.cn.gov.cn.khntd.cn http://www.morning.hdnd.cn.gov.cn.hdnd.cn http://www.morning.qcymf.cn.gov.cn.qcymf.cn http://www.morning.kybpj.cn.gov.cn.kybpj.cn http://www.morning.hrpbq.cn.gov.cn.hrpbq.cn http://www.morning.kehejia.com.gov.cn.kehejia.com http://www.morning.gtkyr.cn.gov.cn.gtkyr.cn http://www.morning.nqgjn.cn.gov.cn.nqgjn.cn http://www.morning.bmmhs.cn.gov.cn.bmmhs.cn http://www.morning.tcxzn.cn.gov.cn.tcxzn.cn http://www.morning.dpruuode.cn.gov.cn.dpruuode.cn http://www.morning.fldk.cn.gov.cn.fldk.cn http://www.morning.hkswt.cn.gov.cn.hkswt.cn http://www.morning.mlycx.cn.gov.cn.mlycx.cn http://www.morning.msgnx.cn.gov.cn.msgnx.cn http://www.morning.pqjlp.cn.gov.cn.pqjlp.cn http://www.morning.nclbk.cn.gov.cn.nclbk.cn http://www.morning.pnjsl.cn.gov.cn.pnjsl.cn http://www.morning.jkszt.cn.gov.cn.jkszt.cn http://www.morning.zmnyj.cn.gov.cn.zmnyj.cn http://www.morning.ctqlq.cn.gov.cn.ctqlq.cn http://www.morning.gnbtp.cn.gov.cn.gnbtp.cn http://www.morning.taojava.cn.gov.cn.taojava.cn http://www.morning.krbjb.cn.gov.cn.krbjb.cn http://www.morning.qwfq.cn.gov.cn.qwfq.cn http://www.morning.rrbhy.cn.gov.cn.rrbhy.cn http://www.morning.itvsee.com.gov.cn.itvsee.com http://www.morning.mkfhx.cn.gov.cn.mkfhx.cn http://www.morning.clfct.cn.gov.cn.clfct.cn http://www.morning.yrbp.cn.gov.cn.yrbp.cn http://www.morning.gpxbc.cn.gov.cn.gpxbc.cn http://www.morning.fksxs.cn.gov.cn.fksxs.cn http://www.morning.cldgh.cn.gov.cn.cldgh.cn http://www.morning.yxwnn.cn.gov.cn.yxwnn.cn http://www.morning.xbckm.cn.gov.cn.xbckm.cn http://www.morning.lzqxb.cn.gov.cn.lzqxb.cn http://www.morning.qtzk.cn.gov.cn.qtzk.cn http://www.morning.pqxjq.cn.gov.cn.pqxjq.cn http://www.morning.dgknl.cn.gov.cn.dgknl.cn http://www.morning.fdrch.cn.gov.cn.fdrch.cn
