解决0-1背包问题（方案一）:二维dp数组

>>确定dp数组以及下标的含义

dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为j的背包，价值总和最大是多少

（1）不放物品i

例如：当背包的容量是1kg，此时物品1和物品2都是无法放进去的。而物品0是可以放进背包的。

那么此种情况下：

物品0，产生的最大的价值为15

物品1，产生的最大的价值和前面相同，也就是15

物品2，产生的最大的价值和前面相同，也就是15

观察二维表格，以及分析，我们可以这样表示：dp[i-1][j]

思考：dp[i-1][j] 表示什么意思呢？

看表格的 j=0，这一列，正是上文所述的这种情况。也就是背包的容量为 j 的时候，可以放入物品i 或者不能放入物品i 的所能产生的最大的价值!

思考：不能放入物品i时，如何计算其产生的最大价值呢？

只要和前面的值相同即可。相当于 copy 下来。

例如物品1（3kg）放不进容量小于3kg的背包。也就是背包容量为1kg,2kg时，无法放入物品1，那么此时这种情况如何计算最大价值呢？很简单，就是和前面的值相同即可。也就是和物品0产生的最大价值相同。

同理，物品2（4kg）放不进容量小于4kg的背包。也就是背包容量为1kg,2kg,3kg时，无法放入物品2，那么此时和物品1产生的最大价值相同即可。

思考：若能放入物品i呢？

分成两种方案：

【方案一】：放入物品i 能产生的最大价值

【方案二】：不放入物品i能产生的最大价值

选取最大价值即可~

例如：当背包的容量是4kg,可以只放入物品2（4kg），但是产生的价值未必是最大的。此时我们思考一下如果不放入物品2，而是放入其他的物品，计算其重量之和为4kg所能产生的价值。

若不放入物品2，可以有如下思路：

① 只放入物品0（1kg），产生价值15

② 只放入物品1（3kg），产生价值20

③ 先放入物品1（3kg），剩余的1kg的容量，用来放入物品0（1kg），总该产生价值35

那么我们如何实现③这种方案呢？

显然，4kg的容量是可以放入物品1（3kg）并可知其产生的价值为20,那么此时可以计算出剩余容量（1kg）,接着在表格中找出1kg能产生的最大价值为15，然后求其价值总和为35。

观察二维表格，以及分析，我们可以这样表示：

所剩容量能产生的最大价值 + 放物品i的价值 -> dp[i-1][j-weight[i]] + value[i]

（2）放入物品i

例如：当背包的容量是4kg,只放入物品2（4kg），产生价值为30

我们可以发现，应该取 max(不放物品i的最大价值，所剩容量能产生的最大价值 + 放物品i的价值)

上文提及不放物品2，而是放入其他物品时，产生的最大价值为35（也就是放入物品0和物品1所产生的最大价值）。35>30。此时我们便可更新背包的容量是4kg时所能 产生的最大价值为35。

最大价值：dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])

*******************两个方向推出dp[i][j]*******************

>>可以从两个方向推出来dp[i][j]

1.由 dp[i-1][j] 推出，即背包容量为j,里面不放物品i的最大价值，此时 dp[i][j] 就是 dp[i-1][j]

2.dp[i-1][j-weight[i]]推出，dp[i-1][j-weight[i]] 为背包容量为 j-weight[j] 的时候不放物品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]);

【问题(O_O)?思考】：请问是先遍历物品还是先遍历背包呢？

【回答】都可以，因为dp[i][j] 的状态是由正上方和左上方的状态推出来的，无论是先遍历物品还是先遍历背包，都可以知道正上方和左上方的状态，因此dp[i][j]的状态可以被推出。那么选取先遍历物品再遍历背包，还是先遍历背包再遍历物品都是可以的！！！

 在代码体现中，都可以的呢！！！(#^.^#)

// 先遍历物品再遍历背包
for() //遍历物品
    for()//遍历背包
 
 
// 先遍历背包再遍历物品
for() //遍历背包
    for()//遍历物品

****************************************************************************

（3）动规五部曲：

1.确定dp数组以及下标的含义

dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为j的背包，价值总和最大是多少

2.确定递推公式

由 dp[i-1][j] 推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i-1][j]

由 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数组的定义吻合，否则到递推公式的时候会乱掉。

从定义出发，若背包容量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] 应该是 value[0]，因为背包容量足够放编号0物品。

dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化为多少呢？

其实从动态递推公式：dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);可以看出 dp[i][j] 是由左上方数值推导出来，那么其他下标初始为什么数值都可以，因为都会被覆盖

初始-1，初始-2，初始100，都可以！

但一开始统一把dp数组统一初始化为0，更方便一些。

dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少 

4.确定遍历顺序

有两个遍历的维度：物品与背包重量

思考🤔：请问是先遍历物品还是先遍历背包重量呢？

其实都可以！！！但是先遍历物品更加容易理解！！！

// weight数组的大小，就是物品的个数
for(int i=1;isize();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]);
    }
}

5.举例推导dp数组

>>完整代码：

#include
#include 
using namespace std;
 
void test_0_wei_bag_problem() {
	vector<int> weight = { 1,3,4 };
	vector<int> value = { 15,20,30 };
	int bagWeight = 4;
	// 二维数组
	vectorint>> dp(weight.size() + 1,vector<int>(bagWeight + 1, 0));
 
	// 初始化
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }
 
	// weight数组的大小，就是物品个数
	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]);
		}
	}
	cout << dp[weight.size() - 1][bagWeight] << endl;
}
 
int main() {
	test_0_wei_bag_problem();
}

>>思考

能否减少一些 copy ？可以 省去背包容量无法放下物品i 的情况时候，和前面值一样的"copy"

// 遍历过程
for(int i=1;isize();i++) { // 遍历物品
    for(int j=0;j<=bagWeight;j++) {
        if(j-weight[i] >= 0) {
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);
        }
    }
}
 
其实就是省去了背包容量无法放下物品i的情况时候，和前面值一样的"copy"

 >>思考

观察这个图，我们可以知道其实有些数值的拷贝是无用的，可以进一步优化呢！

思考：其实不需要在背包容量<物品i的重量的时候，其实就是不需要再去拷贝上一层的数据的。因为从现实意义来说，本来就是放不进去的。所以用一维数组可以实现重复利用这个数值，那么大大节省了空间和运行效率！

优化思路：可以沿用已经计算好的最大值，然后在其基础上进行进一步的更新！！！（即重复利用），也就是说可以将二维dp数组，改进为一维dp数组。在这一篇博客会详细讲解：解决0-1背包问题（方案二）：一维dp数组（滚动数组）_呵呵哒(￣▽￣)"的博客-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133208594?spm=1001.2014.3001.5501

【总结】：对于背包问题其实状态都可以压缩的！！！

来自代码随想录的课堂截图：