卡玛网● 46. 携带研究材料 ● 01背包问题，你该了解这些！ 滚动数组 力扣● 416. 分割等和子集

开始背包问题，���握0-1背包和完全背包即可，注：0-1背包是完全背包的基础。

0-1背包问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。下面是n=4的例子：

如果用穷举方法，应该使用回溯法，那么每个物件都有放一个和不放两种选择，所以回溯的时间复杂度是O(2^n)，达到指数级。所以要使用动态规划。

以这个例题来进行二维dp数组和一维dp数组的动规五部曲：背包最大重量为4。物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

 

● 二维dp数组

1. 确定动规数组元素的含义。使用的是二维数组 dp[i][j]：从物品[0,i]范围内随便选择，放进容量为j的背包里，dp[i][j]是背包的最大价值。如下图所示：

2. 确定递推公式。我们可以根据两种方式得到dp[i][j]，两种方式对应两种情况，其实dp[i][j]就是取这两种情况的最大值。

①不放物品 i。如果物品i放进重量为j的背包会超重，那么不能把i放进去，所以重量设定为j的话，从[0,i-1]选择和从[0,i]选择的最大价值是一样，所以 dp[i][j] = dp[i-1][j] 。

②放物品 i。如果不会超重，可以放进去。物品 i 放进去，背包最大重量为 j ，还没有放进去物品 i 的时候，背包的最大重量为 j - weight[i] ，数量为i-1，所以这时背包的最大价值为 dp[ i-1 ][ j - weight[i] ]。加入物品 i ，背包价值 dp[i][j] 就为 dp[ i-1 ][ j - weight[i] ] + value[i] 。

所以dp[i][j]= max ( dp[i-1][j] , dp[ i-1 ][ j - weight[i] ] + value[i] )。

必须牢记dp[i][j]的含义。

3. 如何初始化。

在上图里面，背包重量j为0的时候，什么也不能放进去，所以这一列肯定都是0。

物品 0 那一行，只能选择物品 0 自己，所以背包重量 j >=物品 0 的重量对应的表格都应该填上物品 0 的价值15.所以初始化后：

4. 遍历顺序。 根据上表，第一行第一列已经初始化，所以 i 应该从1到2，j 从 0 到背包容量4。是先行还是先列呢，其实都一样。先每个物品那一行统计完更好理解一些，但是先列也是从上往下走的，到一个元素的时候，左上角（包括正上方）的dp[i][j]都已经统计完成，所以都可以。背包问题里，两个for循环的先后循序是非常有讲究的。

5. 打印dp数组。

最后的结果就是返回dp[2][4]。

做题巩固一下：

题目链接46. 携带研究材料：题目链接

和上面例题的分析过程一样，使用二维dp数组，代码如下：

void maxValue(){    int m,begweight;//M 代表物品的种类数，begweight是背包容量    cin>>m>>begweight;    vector weight(m);    vector value(m);    //读取重量和价值    for(int i=0;i>weight[i];    }    for(int i=0;i>value[i];    }    //注意行列数    vector dp(m,vector(begweight+1,0));    //初始化    for(int j=0;j