动态规划：二维01背包问题_二维背包

掌握：01背包（出题一般没有纯01背包问题，都是01背包应用方法的题目，需要转化为01背包问题）、完全背包（在01背包上稍作变换，物品数量无限）、（多重背包）

背包分组图：

01背包

---

有n个物品和一个最多装重量为w的背包，第i个物品的重量是weight[i]，价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大？

01背包问题的暴力解就是从底向上思考的回溯法，每个物品只有两个状态，取或者不取，所以可以用回溯法搜索出所有情况，这时时间复杂度就为O(2^n)，n就是物品数量。暴力解法是指数级别的时间复杂度，所以需要动态规划的解法来进行优化。

例子：背包最大重量为4，问背包能背的物品最大价值是多少？

二维dp数组01背包

---

动态规划5部曲：

• 1.确定dp数组及其下标含义
  对于背包问题，有一种写法，是使用二维数组，即dp[i][j]表示从下标从[0,i]里的物品里任意取，放进容量为j的背包，价值总和最大是多少。如下图所示：
  

• 2.确定递推公式
  dp[i][j]的含义是从下标为[0,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得到的最大价值。
  所以，递推公式为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])。

• 3.dp数组如何初始化
  关于初始化，一定要和dp数组的定义吻合，否则递推公式会越来越乱
  首先从dp[i][j]的定义出发，如果j=0的话，即背包容量为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的物品。
  初始化的代码如下：

for(int j=0;j<weight[0];j++)//如果把dp初始为0，则不用写这一部分
{
dp[0][j]=0;
}
for(int j=weight[i];j<=bagweight;j++)//正常遍历
{
dp[0][j]=value[0];
}
1
2
3
4
5
6
7
8

所以，背包初始化为：

这时，dp[0][j]与dp[i][0]都已经初始化了，那么其他下标应该怎么初始化呢？
从递归公式可以看出，dp[i][j]是由左上方数值推导出来的，那么其他下标初始化为什么数值都行，因为都会被覆盖。
初始-1，初始-2，初始100，都可以！
但只不过一开始就统一把dp数组统一初始为0，更方便一些。
最终初始化代码如下：

// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
1
2
3
4
5

• 4.确定遍历顺序
  如下图所示，有两个遍历维度：物品与背包重量
  
  那么，是先遍历物品还是背包重量？
  其实都可以，不过先遍历物品更好理解
  先给出遍历物品，再遍历背包重量的代码

for(int i=1;i<weight.size();i++)//遍历物品
{
for(int j=0;j<=bagweight;j++)//遍历背包重量
{
if(j<weight[i]) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}
}
1
2
3
4
5
6
7
8

先遍历背包重量，再遍历物品的代码：

for(int j=0;j<=bagweight;j++)
{
for(int i=1;i<weight.size();i++)
{
if(j<weight[i]) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}
}
1
2
3
4
5
6
7
8

为什么两个方向都可以？
需要明白，递归的本质和递推的方向。
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]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的过程如图所示：
再来看看先遍历背包，再遍历物品呢，如图：

• 5.举例推导dp数组
  dp数组对应值如下图所示：
  
  最终结果就是dp[2][4]=35。
  完整的C++代码如下：

void test_2_wei_bag_problem1(){
vector<int> weight={1,3,4};
vector<int> value={15,20,30};
//二维数组
vector<vector<int>> dp(weight.size(),vector<int>(bagweight+1,0));
//初始化
for(int j=0;j<=bagweight;j++)
{
dp[0][j]=value[0];
}
//weight数组的大小，就是物品个数
for(int i=1;<weight.size();i++)
{
for(int j=0;j<=bagweight;j++)
{
if(j<weight[i]) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]));
}
}
cout<<dp[weight.size()-1][bagweight]<<endl;
}
int main()
{
test_2_wei_bag_problem1();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结

通过上述讲解发现，01背包中最简单的就是推导公式了，难点在于如何初始化和遍历顺序上。
接下来讲解一维背包与二维背包的异同。