[C++]背包问题：洛谷 采药 01背包模型详解

[原题]

[输入样例]

70 3
71 100
69 1
1 2

[输出样例]

3

[解题思路]

给出M个草药，每个草药分别对应两个参数：草药价值val及采摘时间time，要求不超过T（即最大采摘时间）的时间内能采摘的草药最大总价值为多少（注：每个草药不可重复采摘）。

这是最典型的01背包模型：现有一个容量为C的背包，给出数个物品，每个物品占用固定的容量，拥有固定的价值，你需要对每一个物品作出取（1）或不取（0）的抉择，使得最终获得的总价值最大。

可以看出，本题仅仅是将01背包中的容量改成了时间，当然这并不影响我们用同样的方法解题，接下来，我们就来看看该如何解决这一类问题吧。

-动态规划-

首先，我们可以建立一个类来存储草药的属性（请记住这个类，因为我们后续的代码会用到），代码如下：

class Item
{
public:
	int val;//草药价值
	int time;//所需采摘时间

	Item(int v = 0, int t = 0):val(v),time(t){}
};

为了方便演示，现给出如下样例，思考我们将如何选取草药使得价值最大：

结果显而易见，我们肯定会选择摘取草药2和3，因为草药1的采摘时间>T，我们无法摘取，而选择2+3的组合可达到最大价值6。

现在，假如我们将T提升到6呢？那我们肯定选择只采摘草药1啊，毕竟7>4+2嘛！

由此，我们引出思考：随着T的变化，我们选择的物品组合有可能发生改变，那么在不同的T及物品组合之间，我们能否找出一个合适的关系式，使得我们能通过这个关系式，求出最终的解呢？

接下来，我们通过列表的形式来寻找这个规律。我们建立一个val关于i-T的表格，其中，i代表每种草药在数组中存放的位置（即草药1为0，草药2为1，以此类推），其中每一格代表到目前格为止的最大价值。

我们可以很轻松的完成第一行及第一列的填写，结果如下：

剩下的每一格，我们都遵循这样一个原则：对于每一行的物品i，我们都只考虑小于等于i的物品组合，即在计算物品1某一格的最大价值时，我们只能从物品0和物品1中进行选择并求出本格为止的最大价值，而不考虑物品2。

虽然这个过程些许有些复杂，但是我们还是不难完成下面这张表格：

刚才我们也说过，对于每个物品，我们有且只有两种选择：选or不选，下面我将对这份表格其中的三个单元格进行具体分析，为我们得出递推式做下铺垫：

（1）i=2,T=3：假如我们选择物品2，那么最终的总价值为2；假如我们不选物品2，那么最大总价值就是i=1,T=3对应的最大总价值4，因此结果为max(2,4)=4；

（2）i=2,T=5：假如我们选择物品2，剩下T=5-2=3，我们还可以继续选择物品1，最终总价值为4+2=6；假如我们不选物品2，最大总价值就是i=1,T=5对应的最大总价值4，因此结果为max(6,4)=6；

（3）i=2,T=6：假如我们选择物品2，同上得总价值为6；假如我们不选物品2，最大总价值就是i=1,T=6对应的最大总价值7，因此结果为max(6,7)=7；

通过类比和总结，我们可以发现这样一个规律：

dp[i][T] = max(dp[i - 1][T - items[i].time] + items[i].val, dp[i - 1][T]);

如何理解这个递推式：

当我们选择当前物品i时，我们用T减去物品i的占用时间得到T0，再将dp[i-1][T0]（也就是直到上一个物品时，在T0时间内能取得的最大值）加上物品i的价值，得到一个总价值v1；

当我们不选择当前物品i时，我们继承上一个物品在T处的最大价值，记作v2。

接着，权衡v1和v2的大小，其中较大者作为dp[i][T]的值。

接下来，我们用代码完整地模拟一下上述的整个过程：

#include
#include
using namespace std;

class Item
{
public:
	int val;//草药价值
	int time;//所需采摘时间

	Item(int v = 0,int t = 0):val(v),time(t){}
};

int main()
{
	//读取数据及数组声明
	int T, M;
	cin >> T >> M;
	vector> dp(M, vector(T + 1));
	vector items(M);
	for (int i = 0; i < M; i++)
	{
		int v, t;
		cin >> t >> v;
		items[i] = Item(v, t);
	}

	//初始化首行首列
	for (int i = 0; i < M; i++)
	{
		//T为0时，不采摘草药
		dp[i][0] = 0;
	}
	for (int j = 0; j <= T; j++)
	{
		//若物品0的时间>=当前T的值，则更新为物品0的val
		dp[0][j] = j >= items[0].time ? items[0].val : 0;
	}

	//遍历草药数量及最大时间
	for (int i = 1; i < M; i++)
	{
		for (int j = 1; j <= T; j++)
		{
			if (j - items[i].time >= 0)//越界判断
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i].time] + items[i].val);
		}
	}

	//打印dp的最后一格，即为所求
	cout << dp.back().back();
	return 0;
}

代码时间复杂度为o(n^2)，空间复杂度为o(n^2)。

-动态规划+滑动数组+一些小优化-

首先，让我们再次观察一下这个递推公式：

dp[i][T] = max(dp[i - 1][T - items[i].time] + items[i].val, dp[i - 1][T])

不难发现，在每一行计算的过程中，只出现了i和i-1，也就是说，每次的计算只跟上一行及本行的数据有关，在此之前的所有数据在使用结束后就已经完成了使命。但是，这些没有作用的数据占用了数组中的绝大多数空间，造成了很大的空间浪费。因此，我们可以通过滚动数组对这种现象进行空间上的优化。

那么，滚动数组究竟是什么呢？

相信大家对斐波那契数列的递推程序并不陌生（如果遗忘的话可以参考下面的代码）。

#include
using namespace std;

int main()
{
	int n;
	cin >> n;
	int f0 = 1, f1 = 1;
	for (int i = 1; i <= n; i++)
	{
		if (i < 3)
			cout << 1 << endl;
		else
		{
			int tmp = f0;
			f0 = f1;
			f1 += tmp;
			cout << f1 << endl;
		}
	}
	return 0;
}

在这个程序中，我们通过f0和f1不断迭代和转移数据来实现了对每一项的计算与打印，而并没有新建一个数组存放每一项的值再进行后一项的计算，这种算法使得空间复杂度从o(n)优化到了o(1)。

与这种思想相似，滚动数组，就是通过一个相对低维的数组不断更新数据，从而实现代替高维数组的功能。当然，滚动数组有一个适用条件：旧数据都无需复用，数据的更新不会影响最终结果的计算。

那么这道题的优化也不难想到：既然每行的数据只与本行和上一行的数据有关，我们可以用两个一维数组存放两行的数据，通过数据的不断更新取得最终结果。

这当然没有问题，不过我们可以考虑一个更优的解法：仅用一个一维数组，从后往前更新数据。

那么，为什么只需要一个数组？为什么又要逆序更新数据呢？在讨论这两个问题之前，我们先看下面这张图：

当我们逆序更新数组的时候，更新位置（即箭头所在位置）前的所有数据都是上一行的旧数据，而更新位置后的数据都是这一行的新数据。而观察我们的递推公式，可以发现我们需要的数据 dp[i - 1][T - items[i].time] 和 dp[i - 1][T] 不仅在上一行，而且所在列数也一定小于等于更新位置，因此我们逆序更新数据时仅需一个一维数组就可以保证我们需要的数据不会被覆盖。

这样，滑动数组的优化就完成了。

另外，让我们再次回到刚才的表格。

不难发现，对于每个 items[i] ，所有 T < items[i].time 的单元格都为0，因此我们可以初始化整个数组为0，接着从后往前更新，直到 T == items[i].time 时结束当前轮循环。

对于上面的优化，让我们看一下具体的代码实现：

class Item
{
public:
	int val;
	int time;

	Item() :val(0), time(0) {}
	Item(int v, int t) :val(v), time(t) {}
};

int main()
{
	int T, M;
	cin >> T >> M;
	vector dp(T + 1, 0);
	vector items(M);
	for (int i = 0; i < M; i++)
	{
		int v, t;
		cin >> t >> v;
		items[i] = Item(v, t);
	}

	for (int i = 0; i < M; i++)
	{
		for (int j = T; j >= items[i].time; j--)
		{
			dp[j] = max(dp[j], dp[j - items[i].time] + items[i].val);
		}
	}

	cout << dp.back();
	return 0;
}

显然，无论是代码的长度上，空间复杂度上，还是注释的数量上来看，都得到了显著的优化。