背包问题的重中之重是01背包
01背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！
举一个例子：背包最大重量为4，有3个物品，其重量和价值如下表
物品为：
重量价值物品0115物品1320物品2430
问背包能背的物品最大价值是多少？
动规五部曲
1）确定dp数组以及下标的含义
对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少，i代表第几个物品，j代表背包的容量，dp[i][j]代表价值
2）递推公式
对于每一个物品都有放与不放两种状态，所以又有两种情况，取这两种情况的最大值
3）dp数组初始化
根据递推公式，可知dp数组是由其左上角和正上方推导而来，所以要对其第一行和第一列进行初始化
其他下标的价值由递推公式更新推导，所以其它地方初始化为任意值均可
4）遍历顺序
因为本题有两个维度，分别为物品维度和背包容量维度，所以到底是先遍历物品呢？还是先遍历背包呢？
可以分类讨论一下
先遍历物品
先遍历背包
5）打印dp数组
代码
int weight_bag(vector
vector
//初始化.对于物品0
for(int j=weight[0];j<=bagweight;j++){
dp[0][j]=value[0];
}
//递推（先遍历物品，再遍历背包）
for(int i=1;i for(int j=0;j<=bagweight;j++){ if(j //如果当前物品重量比背包容量小，那么可以有两种选择，装下该物品，或是不装该物品 else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]); } } return dp[weight.size()-1][bagweight]; } 01背包（滚动数组） 把dp[i - 1]这一层拷贝到dp[i]上，只用一个一维数组dp[j]，可以理解是一个滚动数组。 滚动数组需要满足的条件是上一层可以重复利用，直接拷贝到当前层，一直处于一种刷新的状态 动规五部曲 1）确定dp数组的定义 在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。 2）一维dp数组的递推公式 dp[j]有两个选择，一个是不放物品i，取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]；一个是放物品i，取dp[j - weight[i]] + value[i]，取二者当中的最大值 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 3）一维dp数组的初始化 dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。 除了下标0的位置，初始为0，其他下标应该初始化多少呢？ 根据递推公式，dp数组在推导的时候一定是取价值最大的数，那么非0下标都初始化为0就可以了，这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。 4）一维dp数组的遍历顺序 一维dp遍历的时候，背包是从大到小，注意一定要是倒序遍历 倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！ 因为根据递推公式，每个物品只放一次，在遍历物品的时候，变动j时，每次都要刷新dp[j] dp[1]=dp[1-weight[0]]+value[0]=dp[0]+15=0+15=15 dp[2]=dp[2-weight[0]]+value[0]=dp[1]+value[0]=15+15=30,这里物品0会放入两次，因为前面刷新了dp[1]，初始值会被修改，连带着后面的dp[2]会受到波及！！！！ 为什么二维dp数组遍历的时候不用倒序呢？ 因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！，因为是二维数组，没有动态刷新，所以一旦求出数值，便会一直在那保持不变 两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？ 不可以！因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经写了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。 因为是每次只对一个背包容量进行求解， dp[4]=dp[4-1]+value[0]=15 dp[4]=max(15,dp[4-3]+value[1])=max(15,20)=20 dp[4]=max(10,dp[4-4]+value(2))=max(20,30)=30 dp[3]=dp[3-1]+value(0)=value(0)=15 ........ 如上，因为是倒序遍历和初始化的存在，针对每个背包容量，每次都只放进了一个物品，不能将两个或多个物品的情况考虑在内 dp[4]=dp[4-1]+value[0]=15 dp[3]=max(dp[3],dp[3-1]+value[0])=15 dp[2]=max(dp[2],dp[2-1]+value[0])=15 dp[1]=max(dp[1],dp[1-1]+value[0])=15 dp[4]=max(dp[4],dp[4-3]+value[1])=max(15,15+20)=35 ......... 如上，每个背包的容量随着物品的变动与前面每一个物品的情况结合起来，这才是正解 倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。 倾向于使用一维dp数组的写法，比较直观简洁，而且空间复杂度还降了一个数量级！ 代码 int weightvalue(int bagweight,vector //初始化dp数组 vector //递推 for(int i=0;i for(int j=bagweight;j>=weight[i];j--){ dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); } } return dp[bagweight]; } 背包问题应用1 题目：416分割等和子集 题目链接：分割等和子集 对题目的理解 非空数组由正整数组成，是否可以将这个数组分割成两个子集，使得两个子集的元素和相等 将问题具象化：只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。 集合中的元素只能使用一次，因此使用的是01背包 只有确定了如下四点，才能把01背包问题套到本题上来。 背包的容量为sum / 2背包要放入的商品（集合里的元素）重量为nums[i]，价值也为nums[i]背包如果正好装满，说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入 动规五部曲 1）确定dp数组含义及下标 dp[j]:容量为j的背包所背的最大价值为dp[j] 集合中的每个元素既是重量也是价值 dp[target]==target 背包装满 其中target=sum/2 2）递推公式 背包的递推公式：dp[j]=max(dp[j],dp[j-weight[i]]+value[i]) 所以本题的递推公式：dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]) 3）dp数组初始化 dp[0]=0 ，非零下标进行初始化，dp[i]=0,根据递推公式,不能初始化别的值，初始化为非负整数的最小值，即0，这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。 4）遍历顺序 遍历顺序：先正序遍历物品，后倒序遍历背包容量 for(i=0;i for(j=target;j>=nums[i];j--)} 5）打印dp数组 代码 class Solution { public: bool canPartition(vector vector int sum = 0; for(int i=0;i sum += nums[i]; } if(sum % 2==1) return false;//如果和的一半是奇数，那么不可能有两个子集和相等 int target = sum/2; //递推公式 //先正序遍历物品，后倒序遍历背包 for(int i=0;i for(int j=target;j>=nums[i];j--){ dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]); } } if(dp[target]==target) return true; return false; } }; 时间复杂度：O(n^2)空间复杂度：O(n)，虽然dp数组大小为一个常数，但是大常数 文章链接
发表评论