前言

推荐我的博客：《背包详解》

更新日志

To be updated...

什么是背包？

动态规划中的背包问题主要分为01 背包和完全背包两种经典模型：

• 01 背包：每个物品可以选或者不选，即选 $1$ 或 $0$ 次。
• 完全背包：完全背包模型与 01 背包类似，与 01 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

01 背包

例题：洛谷 P2871 [USACO07DEC] Charm Bracelet S 。

有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

看到这题首先想到贪心，然后考虑怎么贪？

按照重量？价值？性价比？我们都很容易想到反例，贪心失败。

然后我们考虑搜索。显然的枚举子集，可是时间复杂度 $O(2^n)$，T 飞了，别想了。但是这样还有 $37$ 分，显然数据水了。

接下来是正解，动态规划。

设 $f_{i,j}$ 为在只能放前 $i$ 个物品的情况下，容量为 j 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 $i$ 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 $f_{i-1,j}$；当其放入背包时，背包的剩余容量会减小 $w_{i}$，背包中物品的总价值会增大 $v_{i}$，故这种情况的最大价值为： $f_{i-1,j-w_{i}}+v_{i}$。

由此可以得出状态转移方程：$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})$。

然后我们就可以顺利的写出代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 13000;
int w[N], v[N], f[N][N], n, m;

int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i];
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			f[i][j] = f[i - 1][j]; 
			if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);  
		}
	}
	cout << f[n][m] << endl;
    return 0;
}

但是，一看 $82$ 分，两个点 MLE。我们充分发挥人类智慧，二位数组可能会炸空间，可以考虑改用滚动数组的形式来优化。

由于对 $f_i$ 有影响的只有 $f_{i-1}$，可以去掉第一维，直接用 $f_{i}$ 来表示处理到当前物品时背包容量为 $i$ 的最大价值，得出以下方程：$f_j=\max \left(f_j,f_{j-w_i}+v_i\right)$。

然后我们就可以顺利的写出代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 13000;
int n, m, w[N], v[N], f[N];

int main()
{
  	cin >> n >> m;
  	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
  	for (int i = 1; i <= n; i++)
    	for (int j = m; j >= w[i]; j--)
      		if (f[j - w[i]] + v[i] > f[j])
			  	f[j] = f[j - w[i]] + v[i];
  	cout << f[m] << endl;
  	return 0;
}

显然可以 AC。

完全背包

完全背包模型与 01 背包类似，与 01 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

我们可以借鉴 01 背包的思路，进行状态定义：设 $f_{i,j}$ 为只能选前 $i$ 个物品时，容量为 $j$ 的背包可以达到的最大价值。

需要注意的是，虽然定义与 01 背包类似，但是其状态转移方程与 01 背包并不相同。

可以发现，对于 $f_{i,j}$，通过 $f_{i,j-w_i}$ 转移即可。因此状态转移方程为：$f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)$。理由是当我们这样转移时，$f_{i,j-w_i}$ 已经由 $f_{i,j-2\times w_i}$ 更新过，那么 $f_{i,j-w_i}$ 就是充分考虑了第 $i$ 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。

然后我们就可以顺利的写出代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5, M = 1e7 + 5;
int n, m, w[N], v[N];
long long f[M];

int main()
{
  	cin >> m >> n;
  	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
  	for (int i = 1; i <= n; i++)
    	for (int j = w[i]; j <= m; j++)
      	if (f[j - w[i]] + v[i] > f[j])
		  	f[j] = f[j - w[i]] + v[i];
  	cout << f[m];
  	return 0;
}

参考文献

• 《01背包与完全背包问题详解》
• OI-Wiki

后记

背包还是比较难的，大家不要急于抄题解，要去理解！

谢谢观看Thanks♪(･ω･)ﾉ