免费cms建站五指,个人如何注册商标,如何做分销型网站,合肥蜀山网站开发01背包理论基础
面试掌握01背包#xff0c;完全背包和重背包就够用了。 背包问题的理论基础重中之重是01背包#xff0c;一定要理解透#xff01; 01 背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品…01背包理论基础
面试掌握01背包完全背包和重背包就够用了。 背包问题的理论基础重中之重是01背包一定要理解透 01 背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是o(2^n)这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化
举例背包最大重量为4。
物品为
重量价值物品0115物品1320物品2430
问背包能背的物品最大价值是多少
以下讲解和图示中出现的数字都是以这个例子为例。
二维数组01背包
依然动规五部曲分析一波。
1. 确定dp数组以及下标的含义
对于背包问题有一种写法 是使用二维数组即dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。要时刻记着这个dp数组的含义下面的一些步骤都围绕这dp数组的含义进行的。 2. 确定递推公式
有两个方向可以推出来dp[i][j]
不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量或背包剩余重量小于i的重量时物品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数组如何初始化
关于初始化一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。i是由i-1推出来的所以i为0的时候就一定要初始化。刚才讨论过j0的情况那么i0时dp[0][j]即存放编号0的物品时各个容量的背包所能存放的最大价值。因此 j weight[0]时dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。若jweight[0]dp[0][j]的值为value[0]。
dp[0][j] 和 dp[i][0] 初始化以后其他位置都会从i-1或者j-weight[i]而来因此都会被不断地覆盖所以初始化为0即可。
4. 确定遍历顺序
在如下图中可以看出有两个遍历的维度物品与背包重量从哪个方向遍历都可以因此我们就从物品开始遍历。 public static void backValue(int[]value, int[] weight, int bagWeight){int numvalue.length;int[][]dpnew int[num][bagWeight1];for(int jweight[0];jbagWeight;j){dp[0][j]value[0];}for(int i1;inum;i){//从物品开始遍历for(int j1;jbagWeight;j){if(jweight[i]) 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]);}}}System.out.println(dp[num-1][bagWeight]);}
一维数组01背包
上面的思路是用二维数组来解决01背包问题还可以用滚动数组来解决即把二维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]一维数组也可以理解是一个滚动数组。
因此动规五部曲分析如下
1. 确定dp数组的定义
在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。
2. 一维dp数组的递推公式
dp[j]为 容量为j的背包所背的最大价值那么如何推导dp[j]呢
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[j] max(dp[j], dp[j - weight[i]] value[i]); 3. 一维dp数组如何初始化
dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]那么dp[0]就应该是0因为背包容量为0所背的物品的最大价值就是0。
那么dp数组除了下标0的位置初始为0其他下标应该初始化多少呢
看一下递归公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);
dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了。
那么我假设物品价值都是大于0的所以dp数组初始化的时候都初始为0就可以了。
4. 一维dp数组遍历顺序
二维dp遍历的时候背包容量是从小到大而一维dp遍历的时候背包是从大到小。
因为倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品0就会被重复加入多次
举一个例子物品0的重量weight[0] 1价值value[0] 15
如果正序遍历
dp[1] dp[1 - weight[0]] value[0] 15
dp[2] dp[2 - weight[0]] value[0] 30
此时dp[2]就已经是30了意味着物品0被放入了两次所以不能正序遍历。
为什么倒序遍历就可以保证物品只放入一次呢
倒序就是先算dp[2]
dp[2] dp[2 - weight[0]] value[0] 15 dp数组已经都初始化为0
dp[1] dp[1 - weight[0]] value[0] 15
所以从后往前循环每次取得状态不会和之前取得状态重合这样每种物品就只取一次了。
为什么二维dp数组遍历的时候不用倒序呢
因为对于二维dpdp[i][j]都是通过上一层即dp[i - 1][j]计算而来本层的dp[i][j]并不会被覆盖
先遍历物品嵌套遍历背包容量那可不可以先遍历背包容量嵌套遍历物品呢不可以
因为一维dp的写法背包容量一定是要倒序遍历原因上面已经讲了如果遍历背包容量放在上一层那么每个dp[j]就只会放入一个物品即背包里只放入了一个物品。
倒序遍历的原因是本质上还是一个对二维数组的遍历并且右下角的值依赖上一层左上角的值因此需要保证左边的值仍然是上一层的从右向左覆盖。
⚠️一维和二维的区别1一维到序遍历二维正序遍历2一维只能先遍历物品再遍历背包但是二维两个顺序都可。
public static void getBackValue(int[]value, int[] weight, int bagWeight){int numvalue.length;int[]dpnew int[bagWeight1];for(int jweight[0];jbagWeight;j){dp[j]value[0];}for(int i1;inum;i){//从物品开始遍历for(int jbagWeight;jweight[i];j--){//要倒序遍历dp[j]Math.max(dp[j], dp[j-weight[i]]value[i]);}}System.out.println(dp[bagWeight]);}
416. 分割等和子集 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集. 提示 1 nums.length 2001 nums[i] 100 这道题希望能够将一个数组拆成两个子集a和b使得a里面的元素和等于b里面的元素和。
没有什么思路直接看了代码随想录。原来是01背包问题的变种。
01背包问题有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
注意题目描述中商品是不是可以重复放入。一个商品如果可以重复多次放入是完全背包而只能放入一次是01背包。 要明确本题中我们要使用的是01背包因为元素我们只能用一次。
回归主题首先本题要求集合里能否出现总和为 sum / 2 的子集。这一点是我没有想到的
那么来一一对应一下本题看看背包问题如何来解决。
只有确定了如下四点才能把01背包问题套到本题上来 背包的可容纳的重量为sum / 2背包要放入的商品集合里的元素重量为元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入
dp[j]表示背包总容量是j放进物品后背包的最大价值为dp[j]。
那么如果背包需要满足的容量为target当dp[target]target时背包就装满了
class Solution {/**背包的可容纳的重量为sum / 2背包要放入的商品集合里的元素重量为元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入*/public boolean canPartition(int[] nums) {int sum0;for(int i0;inums.length;i){sumnums[i];}if(sum%21) return false;int targetsum/2;//weight[i]和value[i]都是nums[i]当前的bacWeight为targetint[] dpnew int[target1];for(int jnums[0];jtarget;j){dp[j]nums[0];}for(int i1;inums.length;i){ //先遍历物品for(int jtarget;jnums[i];j--){//重量要倒序遍历dp[j]Math.max(dp[j], dp[j-nums[i]]nums[i]);}}if(dp[target]target) return true;return false;}
}
