代码随想录day35--动态规划的应用2||01背包理论基础、携带研究材料

01背包理论基础

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i],得到的价值为

value[i]。每件物品只能用一次，将这些物品装入背包里物品价值总和最大。

这是很标准的背包问题，很多同学看到后很自然的就想到了背包，我们要知道为什么用背包问题，也就是动态规划求解，如果使用回溯算法进行求解，搜索出所有的情况，那么时间复杂度就是：

O(n^2)，这里的n表示物品数量。

所以暴力的解法是指数级别的时间复杂度，进而需要动态规划的解法来进行优化

下面，举一个经典的背包问题的例子：

背包最大重量为4.

物品为：

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

首先使用二维dp数组解决

依旧还是动态规划五部曲

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

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

可以结合图表来分析二维数组的定义

dp数组的定义，一定要明确，因为之后的步骤都在围绕dp数组的含义进行分析和操作

如果有些想不通，或者懵逼，那就回顾一下i代表什么，j又代表什么

2.确定递推公式

根据dp[i][j]的含义，可以推导出，可以由两个方向推导出dp[i][j]

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

dp[i-1][j]。(其实就是当物品i的重量大于背包j的重量时，物品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的话，即dp[i][0]，无论选取哪些物品，背包价值一定为0.如图

从状态转移方程中可以看出，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 i = 0 ; i < weight[0]; i++) {  
    dp[i][0] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

dp[i][0]和dp[0][j]都已经初始化完毕，然后就开始其他下标的初始化，其实已经不用再继续初始化了，因为从递推公式来看，已经可以知道，无论初始化任何值，都会被覆盖

4.确定遍历顺序

这道题中，有两个遍历维度：物品与背包重量

那么问题来了，是先比哪里物品还是先遍历背包重量呢？

其实都可以，但是先遍历物品会更好理解

5.举例推导dp数组

先看看推导对应的数值，如图：

建议大家在自己的纸上推导一遍，看看每个元素是不是这样

做动态规划的题目，最好的过程就是自己在纸上推导一遍，如果推导明白了，代码写出来就算有问题，只要把dp数组打印出来，对比一下和自己推导的有什么差异，很快的可以发现问题了

以上，就是求解01背包问题，使用二维dp数组的求解过程了

一维dp数组（滚动数组）

对于背包问题，其实状态是可以压缩的

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i-1][j-weight[i]]+value[i])

其实可以发现如果把dp[i-1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j],dp[i-weight[i]]+value[i];

所以我们发现就可以使用一维数组

这就是滚动数组的又来，需要满足的条件是上一层可有重复利用，直接拷贝到当前层

动规五部分分析如下：

1.确定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[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就是0，因为背包容量为0，所以最大容量就算0

dp数组在推导的时候一定取的是价值最大的数，如果题目给的价值都是正整数，那么非0下标都初始化为0就可以了

这就不会被初始值覆盖了

4.一维dp数组遍历顺序

代码如下

for(int i = 0;i < weight.size();i++){//遍历物品
    for(int j = bagWeight;j >= weight[i];j--){//比哪里背包容量
        dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);
    }
}

需要注意的是，这里的写法，与比哪里背包的顺序是不一样的

二维数组遍历的时候，背包容量是从小到大，而一维数组遍历的时候，背包是从大到小

一维数组中倒序遍历是为了保证物品i只被放入了一次。如果是正序遍历，那么物品0就会被重复加入多次

那么问题来了，为什么二维dp数组是时候不使用倒序呢？

因为对于二维dp，dp[i][j]都是通过上一层即 dp[i-1][j]计算而来，这一层的的dp[i][j]不会被覆盖

还有一个问题，不论是二维数组还是一维数组，都是遍历物品和遍历背包容量，

二维数组中可以使用遍历物品嵌套遍历背包容量，以及遍历背包容量嵌套遍历物品遍历

那么一维数组中是否可以呢？答案是不可以

一维数组中，背包容量一定要倒序遍历，所以一定是遍历物品嵌套遍历背包容量

5.举例推导dp数组

与二维dp数组一致

以上就是01背包问题求解的两种方法，接下来，让我们使用例题来进一步掌握

携带研究材料

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。 

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。 

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例

6 1
2 2 3 1 5 2
2 3 1 5 4 3

输出示例

5

解题思路就是按照我们之前说的基础理论部分进行推导，这里就不做过多赘述了

代码如下

#include <iostream>
#include <vector>

using namespace std;

int n, bagweight;//bagweight表示背包容量
void solve() {
	vector<int> value(n, 0);//每个物品所占空间
	vector<int> weight(n, 0);//每个物品价值
	for (int j = 0; j < n; j++)
		cin >> weight[j];
	for (int i = 0; i < n; i++)
		cin >> value[i];

	vector<vector<int>> dp(weight.size(), vector<int>(bagweight+1, 0));//定义dp数组，dp[i][j]代表行李箱空间为j情况下，从下标为[0,i]的物品中能达到的最大值

	for (int j = weight[0]; j <= bagweight; j++)//初始化，dp[i][0]已经在数组定义中被初始化为0
		dp[0][j] = value[0];
	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];//如果装不下就继承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() {
	while (cin >> n >> bagweight) {
		solve();
	}
	return 0;
}

这是二维dp数组进行推导的解题方法，下面是一维dp数组经推导的解题方法

代码如下

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int M, N;
	cin >> M >> N;

	vector<int> costs(M);
	vector<int> values(M);

	for (int i = 0; i < M; i++)
		cin >> costs[i];
	for (int j = 0; j < M; j++)
		cin >> values[j];

	vector<int> dp(N + 1, 0);//初始化为0

	for (int i = 0; i < M; i++) {//遍历每个类型的研究材料
		for (int j = N; j >= costs[i]; j--) {//从N给空间开始减少当前研究材料所占空间
			dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
		}
	}

	cout << dp[N] << endl;
	return 0;
}

总结

·我们可以发现一维dp数组的写法比较直观，而且空间复杂度还降低了一个数量级

·01背包问题的理解基础就已经说完了，从dp数组定义、递推公式、初始化、遍历顺序到二维数组到一维数组都深刻的剖析了一遍，大家要将这篇内容吃透，后面再做01背包类型的题目就会很简单。我们是有着自己的思考，一步一步推导，了解了他的本质，代码的方方面面都在自己的掌握之下