【算法笔记】三种背包问题——背包 DP

前言

背包Knapsack问题是经典的动态规划问题也很有实际价值。

01背包

洛谷 P2871 [USACO07DEC] Charm Bracelet S
AtCoder Educational DP Contest D - Knapsack 1
有$n$个物品和一个总容量为$W$的背包。第$i$件物品的重量是$w_i$价值是$v_i$。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量且价值总和最大。

这是最原始的01背包问题即每个物品只能选$0$或$1$次。下面我们来看如何求解。
令$f_{i,j}$表示只考虑前$i$个物品的情况下容量为$j$的背包所能装的最大总价值。则最终答案为$f_{n,W}$状态转移方程为
$$f_{i,j}=\{\begin{array}{ll}0& (i=0/j=0)\\ \max (f_{i-1,j},f_{i-1,j-w_i}+v_i)& (i>0,j\ge w_i)\end{array}$$
依次递增$i$逐步增加问题规模即可求解。时间、空间复杂度均为$\mathcal{O}(nW)$。
在本题中$\mathcal{O}(nW)$的空间复杂度容易MLE因此考虑使用数组重复利用或者滚动表的优化。

压缩掉$f$的第一维变成
$$f_j=\max (f_j,f_{j-w_i}+v_i)$$
此时空间复杂度为$\mathcal{O}(W)$。
一定要牢记这个公式注意使用时需倒序枚举$j$防止串连转移。参考代码

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

int f[12881];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(n--)
	{
		int w, v;
		scanf("%d%d", &w, &v);
		for(int i=m; i>=w; i--)
			setmax(f[i], f[i - w] + v);
	}
	printf("%d\n", f[m]);
	return 0;
}

01背包还有一种简单变形即求最小剩余空间此时用$($总空间$-$最大可装空间$)$即可。

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

int f[20005];

int main()
{
	int n, v;
	scanf("%d%d", &v, &n);
	while(n--)
	{
		int w;
		scanf("%d", &w);
		for(int i=v; i>=w; i--)
			setmax(f[i], f[i - w] + w);
	}
	printf("%d\n", v - f[v]);
	return 0;
}

扩展对付更大的$W$

AtCoder Educational DP Contest E - Knapsack 2
本题和普通的01背包完全相同只是数据范围改为$n\le 100,W\le 10^9,v_i\le 10^3$。

注意数据范围$W\le 10^9$意味着只要开这么大的数组都会MLE因此我们考虑修改dp状态。前看原来的dp状态本质上就是“确定重量求最大价值”现在我们反过来即“确定价值求最小重量”。令$f_{i,j}$表示只用前$i$个物品达到总价值为$j$所需的最小空间。由于$n\le 100,v_i\le 10^3$所以$\sum v_i\le 10^5$极限情况下dp数组只需要开$n\times \sum v_i\approx 10^7$即可相对而言会好很多。下面考虑dp状态转移方程
$$f_{i,j}=\{\begin{array}{ll}+\infty & (i=0,j\ne 0)\\ 0& (i\ge 0,j=0)\\ \min (f_{i-1,j},f_{i-1,j-v_i}+w_i)& (i>0,j>0)\end{array}$$
其中$i=0,j\ne 0$这种情况不存在所以初始值为$+\infty$。最终答案即为最大的$j$使得$f_{n,j}\le W$更新状态时可同时记录这个答案。

这种算法的时间和空间都可以优化

• 时间对于每个$i$循环迭代$j$时只需到$v_1+v_2+\cdots +v_i$即可因为当前的总价值不可能超过这个值
• 空间用与前面完全相同的方法压缩掉第一维空间变成$f_j=\min (f_j,f_{j-v_i}+w_i)$注意要倒序枚举$j$

运用了两种优化的代码如下

#include <cstdio>
#include <cstring>
using namespace std;

long long f[100005], t, tot, ans;

int main()
{
	int n, sz;
	scanf("%d%d", &n, &sz);
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	while(n--)
	{
		int w, v;
		scanf("%d%d", &w, &v);
		tot += v;
		for(int i=tot; i>=v; i--)
			if((t = f[i - v] + w) < f[i] && t <= sz)
			{
				f[i] = t;
				if(i > ans) ans = i;
			}
	}
	printf("%lld\n", ans);
	return 0;
}

完全背包

洛谷 P1616 疯狂的采药
有$n$个物品和一个总容量为$W$的背包。第$i$件物品的重量是$w_i$价值是$v_i$。每个物品可以使用无限次。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量且价值总和最大。

这种背包与01背包唯一的不同之处在于每个物品使用次数不限所以参考01背包的dp状态
令$f_{i,j}$表示只考虑前$i$个物品的情况下容量为$j$的背包所能装的最大总价值则有
f i , j = max ⁡ k = 0 + ∞ { f i − 1 , j − k × w i } + v i × k = max ⁡ k = 0 ⌊ j w i ⌋ { f i − 1 , j − k × w i } + v i × k \begin{aligned} f_{i,j}=\max_{k=0}^{+\infin}\{f_{i-1,j-k\times w_i}\}+v_i\times k\\ =\max_{k=0}^{\lfloor\frac j{w_i}\rfloor}\{f_{i-1,j-k\times w_i}\}+v_i\times k \end{aligned} fi,j​=k=0max+∞​{fi−1,j−k×wi​​}+vi​×k=k=0max⌊wi​j​⌋​{fi−1,j−k×wi​​}+vi​×k​
可以发现实际上只需要用$f_{i,j}=\max (f_{i-1,j},f_{i,j-w_i}+v_i)$即可因为此时的$f_{i,j-w_i}$会被$f_{i,j-2w_i}$更新$f_{i,j-2w_i}$又会被$f_{i,j-3w_i}$更新以此类推这样算与前面的公式等效。

对比一下01背包和完全背包的状态转移方程
$$\begin{array}{r}{f}_{i,j}=\max (f_{i-1,j},f_{i-1,j-w_i}+v_i)\\ f_{i,j}=\max (f_{i-1,j},f_{i,j-w_i}+v_i)\end{array}$$
实际上区别就在于一个是$f_{i-1,j-w_i}$一个是$f_{i,j-w_i}$。所以仍可以使用数组压缩只需要改变一下循环顺序是不是很神奇
long long别忘了~

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

long long f[10000005];

int main()
{
	int sz, n;
	scanf("%d%d", &sz, &n);
	while(n--)
	{
		int w, v;
		scanf("%d%d", &w, &v);
		for(int i=w; i<=sz; i++)
			setmax(f[i], f[i - w] + v);
	}
	printf("%lld\n", f[sz]);
	return 0;
}

多重背包

洛谷 P1776 宝物筛选
有$n$个物品和一个总容量为$W$的背包。第$i$件物品的重量是$w_i$价值是$v_i$最多能选择$m_i$次。我们要选择一些物品使这些物品的重量总和不超过背包容量且价值总和最大。$n\le 100,\sum m_i\le 10^5,W\le 4\times 10^4$。

很容易想到可以转换成每件物品都被拆分成$m_i$个只能选一次的物品即$N=\sum m_i$的01背包。很明显这样做的时间复杂度是$\mathcal{O}(W\sum m_i)$会TLE。因此我们可以优化拆分的方法将$m$转化为$x+\sum _{j=0}^i{2}^j$的形式举几个栗子

• $5=(1+2)+2$其中$i=1,x=2$
• $16=(1+2+4+8)+1$其中$i=3,x=1$
• $31=(1+2+4+8+16)$其中$i=4,x=0$。

这种方法的正确性这里就不详细说明了主要依赖于二进制的拼凑。容易发现数字$m$按这种拆分的方法会被拆分为$\lceil {\log }_{2}m\rceil$个数字的和因此总时间复杂度为$\mathcal{O}(W\sum _{i=1}^n\log m_i)$可以通过此题。

还有一种单调队列/单调栈优化同样针对多重背包问题时间复杂度为$\mathcal{O}(nW)$有时不一定优于二进制优化这里就不多说了。下面给出二进制优化的参考程序。

#include <cstdio>
#define maxw 40004
#define setmax(x, y) if(x < y) x = y
using namespace std;

int n, w, f[maxw];

inline void add(int a, int b) // a: value, b: weight
{
	for(int i=w; i>=b; i--)
		setmax(f[i], f[i - b] + a);
}

int main()
{
	scanf("%d%d", &n, &w);
	while(n--)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		for(int i=0; (1<<i)<=c; i++)
			add(a << i, b << i), c -= 1 << i;
		if(c) add(a * c, b * c);
	}
	printf("%d\n", f[w]);
	return 0;
}

混合背包

没错就是前三种放在一起的背包。不用的物品有不同的种类。比如洛谷 P1833 樱花就是混合背包。不过也不要慌直接用个分支判断比如

for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}

实际上也不一定要这样可以全部统一成混合背包

• 对于01背包可选数目$k_i=1$。
• 对于完全背包可选数目$k_i=\lceil \frac{W}{w_i}\rceil$。

这里就不给出详细代码有兴趣的读者可以自己尝试一下。

总结

让我们来总结一下三种基本背包DP的异同

项目	01背包	完全背包	多重背包
适用场景	每件物品只能选择一次	每件物品可以无限选择	每件物品可以选择的次数有限
状态转移方程1	$\max (f_j,f_{j-w_i}+v_i)$	$\max (f_j,f_{j-w_i}+v_i)$	基本同01背包
时间复杂度2	$\mathcal{O}(nW)$	$\mathcal{O}(nW)$	$\mathcal{O}(W\sum \log k_i)$
空间复杂度3	$\mathcal{O}(W)$	$\mathcal{O}(W)$	$\mathcal{O}(W)$
编码难度	低	低	中

创作不易如果觉得好就请给个三连谢谢支持

---

1. 压缩掉第一维的$f_j$01背包为倒序枚举$j$完全背包为正序 ↩︎

2. 完全背包为优化后的复杂度多重背包为二进制优化的复杂度。 ↩︎

3. 指压缩第一维后的dp数组大小。 ↩︎