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

  • A+

前言

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

01背包

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

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

这是最原始的01背包问题(即每个物品只能选 0 0 0 1 1 1次)。下面我们来看如何求解。
f i , j f_{i,j} fi,j表示只考虑前 i i i个物品的情况下,容量为 j j j的背包所能装的最大总价值。则最终答案为 f n , W f_{n,W} fn,W,状态转移方程为:
f i , j = { 0 ( i = 0 / j = 0 ) max ⁡ ( f i − 1 , j , f i − 1 , j − w i + v i ) ( i > 0 , j ≥ w i ) f_{i,j}=\begin{cases} 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{cases} fi,j={
0max(fi1,j,fi1,jwi+vi)(i=0/j=0)(i>0,jwi)

依次递增 i i i,逐步增加问题规模即可求解。时间、空间复杂度均为 O ( n W ) \mathcal O(nW) O(nW)
在本题中, O ( n W ) \mathcal O(nW) O(nW)的空间复杂度容易MLE,因此考虑使用数组重复利用或者滚动表的优化。

压缩掉 f f f的第一维,变成:
f j = max ⁡ ( f j , f j − w i + v i ) f_j=\max(f_j,f_{j-w_i}+v_i) fj=max(fj,fjwi+vi)
此时空间复杂度为 O ( W ) \mathcal O(W) O(W)
一定要牢记这个公式,注意使用时需倒序枚举 j j 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 W W

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

注意数据范围, W ≤ 1 0 9 W\le 10^9 W109意味着只要开这么大的数组都会MLE,因此我们考虑修改dp状态。前看原来的dp状态,本质上就是“确定重量,求最大价值”,现在我们反过来,即“确定价值,求最小重量”。令 f i , j f_{i,j} fi,j表示只用前 i i i个物品,达到总价值为 j j j所需的最小空间。由于 n ≤ 100 , v i ≤ 1 0 3 n\le 100,v_i\le 10^3 n100,vi103,所以 ∑ v i ≤ 1 0 5 \sum v_i\le 10^5 vi105,极限情况下dp数组只需要开 n × ∑ v i ≈ 1 0 7 n\times\sum v_i\approx10^7 n×vi107即可,相对而言会好很多。下面考虑dp状态转移方程:
f i , j = { + ∞ ( i = 0 , j ≠ 0 ) 0 ( i ≥ 0 , j = 0 ) min ⁡ ( f i − 1 , j , f i − 1 , j − v i + w i ) ( i > 0 , j > 0 ) f_{i,j}=\begin{cases} +\infin & (i=0,j\ne0) \\ 0 & (i\ge 0,j=0) \\ \min(f_{i-1,j},f_{i-1,j-v_i}+w_i) & (i>0,j>0) \end{cases} fi,j=

+0min(fi1,j,fi1,jvi+wi)(i=0,j=0)(i0,j=0)(i>0,j>0)

其中, i = 0 , j ≠ 0 i=0,j\ne 0 i=0,j=0这种情况不存在,所以初始值为 + ∞ +\infin +。最终答案,即为最大的 j j j,使得 f n , j ≤ W f_{n,j}\le W fn,jW,更新状态时可同时记录这个答案。

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

  • 时间:对于每个 i i i,循环迭代 j j j时只需到 v 1 + v 2 + ⋯ + v i v_1+v_2+\dots+v_i v1+v2++vi即可,因为当前的总价值不可能超过这个值;
  • 空间:用与前面完全相同的方法,压缩掉第一维空间,变成 f j = min ⁡ ( f j , f j − v i + w i ) f_j=\min(f_j,f_{j-v_i}+w_i) fj=min(fj,fjvi+wi)(注意要倒序枚举 j j 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 n n个物品和一个总容量为 W W W的背包。第 i i i件物品的重量是 w i w_i wi,价值是 v i v_i vi每个物品可以使用无限次。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

这种背包与01背包唯一的不同之处在于,每个物品使用次数不限,所以参考01背包的dp状态:
f i , j f_{i,j} fi,j表示只考虑前 i i i个物品的情况下,容量为 j j 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+{
fi1,jk×wi}+vi×k
=k=0maxwij{
fi1,jk×wi}+vi×k

可以发现,实际上只需要用 f i , j = max ⁡ ( f i − 1 , j , f i , j − w i + v i ) f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i) fi,j=max(fi1,j,fi,jwi+vi)即可,因为此时的 f i , j − w i f_{i,j-w_i} fi,jwi会被 f i , j − 2 w i f_{i,j-2w_i} fi,j2wi更新, f i , j − 2 w i f_{i,j-2w_i} fi,j2wi又会被 f i , j − 3 w i f_{i,j-3w_i} fi,j3wi更新,以此类推,这样算与前面的公式等效。

对比一下01背包和完全背包的状态转移方程:
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 ) \begin{aligned} 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{aligned} fi,j=max(fi1,j,fi1,jwi+vi)fi,j=max(fi1,j,fi,jwi+vi)
实际上,区别就在于一个是 f i − 1 , j − w i f_{i-1,j-w_i} fi1,jwi,一个是 f i , j − w i f_{i,j-w_i} fi,jwi。所以仍可以使用数组压缩,只需要改变一下循环顺序,是不是很神奇?
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 n n个物品和一个总容量为 W W W的背包。第 i i i件物品的重量是 w i w_i wi,价值是 v i v_i vi最多能选择 m i m_i mi。我们要选择一些物品,使这些物品的重量总和不超过背包容量,且价值总和最大。 n ≤ 100 , ∑ m i ≤ 1 0 5 , W ≤ 4 × 1 0 4 n\le100,\sum m_i\le10^5,W\le 4\times10^4 n100,mi105,W4×104

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

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

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

还有一种单调队列/单调栈优化,同样针对多重背包问题,时间复杂度为 O ( n W ) \mathcal O(nW) 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=1 ki=1
  • 对于完全背包,可选数目 k i = ⌈ W w i ⌉ k_i=\lceil\frac W{w_i}\rceil ki=wiW

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

总结

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

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

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


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

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

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

w3cjava

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: