背包 DP

之前打 ABC 发现自己背包掌握的不是很熟练，所以写这一篇复习笔记。

基本模型

有 nn 种物品和一个容量为 mm 的背包，每种物品有重量 wiw_i 与价值 viv_i 两种属性，要求选若干个物品，使它们的重量之和 ≤m\le m 且 ∑v\sum v 最大。

各种背包都是在这个模型下的。

01 背包

每种物品有且仅有一个。

设 dpi,jdp_{i, j} 表示前 ii 种物品，容量为 jj 的背包最大价值。

则

dpi,j=max⁡(dpi−1,j,dpi−1,j−wi+vi)dp_{i, j}=\max(dp_{i-1,j}, dp_{i-1,j-w_i}+v_i)

这里的两种选择对应选 / 不选第 ii 种物品。

可以滚动数组优化。内层循环需要 jj 从 mm 逆向枚举到 wiw_i，防止 dpjdp_j 被 dpj−widp_{j-w_i} 影响。

如此，时间 O(nm)O(nm)，空间 O(m)O(m)。

P2871 [USACO07DEC] Charm Bracelet S

板子一个。代码如下：

1
2
3
4
5
6
7
8
9
10
11
const int N = 13000;
int n, m, w[N], v[N], dp[N];

void _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--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	}
	cout << dp[m];
}

P1855 榨取kkksc03

这题与普通背包的区别在于一种物品有两个体积，在 dpdp 数组中多开一维即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
const int N = 205;
int n, m1, m2, w1[N], w2[N], dp[N][N];

void _main() {
	cin >> n >> m1 >> m2;
	for (int i = 1; i <= n; i++) cin >> w1[i] >> w2[i];
	for (int i = 1; i <= n; i++) {
		for (int j = m1; j >= w1[i]; j--) {
			for (int k = m2; k >= w2[i]; k--) dp[j][k] = max(dp[j][k], dp[j - w1[i]][k - w2[i]] + 1);
		}
	}
	cout << dp[m1][m2];
}

P1802 5 倍经验日

01 背包简单变形。仍然沿用 dpdp 状态，则

dpj=max⁡(dpj+losei,dpj−usei+wini)dp_j=\max(dp_j+lose_i,dp_{j-use_i}+win_i)

注意 j<useij < use_i 时第二个转移无法进行。

1
2
3
4
5
6
7
8
9
10
11
const int N = 1e3 + 5;
int n, m, v1[N], v2[N], w[N], dp[N];

void _main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v2[i] >> v1[i] >> w[i];
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= 0; j--) dp[j] = max(dp[j] + v2[i], j < w[i] ? 0 : dp[j - w[i]] + v1[i]);
	}
	cout << 5LL * dp[m];
}

[ABC390E] Vitamin Balance

三种 ViV_i 分开跑 01 背包，暴力枚举两种 ViV_i 所占的体积，合并答案即可。复杂度 O(nx+n2)O(nx+n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int N = 5005;

int n, x, opt;
int n1, n2, n3;
struct node {
	int v, w;
} a1[N], a2[N], a3[N];
int dp1[N], dp2[N], dp3[N];

void backpack01(node* a, int n, int* dp) {
	for (int i = 1; i <= n; i++) {
		for (int j = x; j >= a[i].w; j--) dp[j] = max(dp[j], dp[j - a[i].w] + a[i].v);
	}
}

void _main() {
	cin >> n >> x;
	for (int i = 1; i <= n; i++) {
		cin >> opt;
		if (opt == 1) n1++, cin >> a1[n1].v >> a1[n1].w;
		if (opt == 2) n2++, cin >> a2[n2].v >> a2[n2].w;
		if (opt == 3) n3++, cin >> a3[n3].v >> a3[n3].w;
	}
	backpack01(a1, n1, dp1);
	backpack01(a2, n2, dp2);
	backpack01(a3, n3, dp3);
	int res = 0;
	for (int i = 1; i <= x; i++) {
		for (int j = 1; j <= x; j++) {
			int k = x - i - j;
			if (k < 0) continue;
			res = max(res, min(dp1[i], min(dp2[j], dp3[k])));
		}
	}
	cout << res;
}

P2340 [USACO03FALL] Cow Exhibition G

把智商当体积，情商当价值，跑完 01 背包合并答案即可。为了处理负数，进行一个数组漂移的 trick。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 1e5;

int n, w[500], v[500], dp[(N << 2) + 5];

void _main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	memset(dp, 0xcf, sizeof(dp));
	dp[N] = 0;
	for (int i = 1; i <= n; i++) {
		if (w[i] >= 0)   
			for (int j = (N << 1); j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		else    // 负数要逆向转移，改成正数以后正序枚举
			for (int j = 0; j <= (N << 1) + w[i]; j++) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	}
	int res = 0;
	for (int i = N; i <= (N << 1); i++) {
		if (dp[i] >= 0) res = max(res, i - N + dp[i]);
	}
	cout << res;
}

P2946 [USACO09MAR] Cow Frisbee Team S

背包经典变式。

模 mm 同余类的背包问题，一般设 dpi,jdp_{i,j} 表示前 ii 种物品，总价值模 mm 等于 jj。这里 dpi,jdp_{i,j} 表示方案数。

那么有转移

dpi,j=dpi−1,j+dpi−1,(j−wi) mod mdp_{i,j}=dp_{i-1,j}+dp_{i-1,(j-w_i)\bmod m}

会发现其实和普通 01 背包的区别就是多模了个 mm。一年前写的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int mod = 1e8;
int n, k, a[N], dp[N][N];

void _main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) dp[i][a[i] % k] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < k; j++) {
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
			dp[i][j] = (dp[i][j] + dp[i - 1][(j - a[i] % k + k) % k]) % mod;
		}
	}
	cout << dp[n][0];
	return 0;
}

P4141 消失之物

直接跑背包计数，复杂度是 O(n2m)O(n^2m) 的。正解用到背包的撤销 trick。

作转移 dpj←dpj+dpj−widp_j \gets dp_j+dp_{j-w_i} 时，我们加入了物品 ii。那么删去物品 ii 就是作 dpj←dpj−dpj−widp_j \gets dp_j-dp_{j-w_i}。代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 2005;
int n, m, w[N], dp1[N], dp2[N];

void _main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i];
	dp1[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= w[i]; j--) {
			dp1[j] += dp1[j - w[i]];
			dp1[j] %= 10;
		}
	}
	for (int i = 1; i <= n; i++) {
		memcpy(dp2, dp1, sizeof(dp1));
		for (int j = w[i]; j <= m; j++) {
			dp2[j] -= dp2[j - w[i]];
			dp2[j] = (dp2[j] + 10) % 10;
		}
		for (int j = 1; j <= m; j++) cout << dp2[j];
		cout << '\n';
	}
	return 0;
}

HDU 2639 Bone Collector II

01 背包，kk 优解问题。

考虑多加一维，令 dpi,j,kdp_{i,j,k} 表示前 ii 种物品，容量为 jj 的背包第 kk 大价值。转移时，要求合并 dpi−1,jdp_{i-1,j} 与 dpi−1,j−wi+vidp_{i-1,j-w_i}+v_i 两个递减序列，取前 kk 大值。这里可以使用某些数据结构或双指针法。这样做时间 O(nmk)O(nmk)，空间 O(mk)O(mk)。

完全背包

每种物品有无数个。

仍然设 dpi,jdp_{i, j} 表示前 ii 种物品，容量为 jj 的背包最大价值。

则

dpi,j=max⁡(dpi−1,j,dpi,j−wi+vi)dp_{i, j}=\max(dp_{i-1,j}, dp_{i,j-w_i}+v_i)

这个转移成立的理由是，dpi,j−widp_{i,j-w_i} 已经被 dpi,j−kwidp_{i,j-kw_i} 所更新过，其中 kk 是不小于 22 的整数。因此，我们取 max⁡\max 的时候已经考虑了当前物品取 [1,k][1,k] 个的情况。

继续滚动数组优化。注意到将 01 背包的内层循环改为正向枚举，即可让 dpjdp_{j} 被 dpj−kwidp_{j-kw_i} 更新。

仍然时间 O(nm)O(nm)，空间 O(m)O(m)。

P1616 疯狂的采药

板子 +1，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
const int N = 1e7 + 5;

long long n, m, w[N], v[N], dp[N];

void _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++) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	}
	cout << dp[m];
}

P1853 投资的最大效益

比较裸的多测完全背包。注意到 aa 是 10001000 的倍数，可以优化一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 1e6 + 5;
int m, y, n, w[50], v[50], dp[N];

void _main() {
	cin >> m >> y >> n; 
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i], w[i] /= 1000;
	long long cur = m;
	while (y--) {
		memset(dp, 0, sizeof(dp));
		int m1 = cur / 1000;
		for (int i = 1; i <= n; i++) {
			for (int j = w[i]; j <= m1; j++) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
		cur += dp[m1];
	}
	cout << cur;
}

多重背包

每种物品有 cic_i 个。

一个朴素的想法是把第 ii 种物品拆分成 cic_i 种只有一个的物品，跑 01 背包。复杂度为 O(m∑ci)O(m\sum c_i)，显然喜提 TLE。

经典的优化是二进制分组。对一个数字 cic_i，把它按二进制拆成 ci=∑2dc_i = \sum 2^d，那么若干个 2d2^d 的和可以表示 [0,ci][0,c_i] 的任意数字，证明使用二进制显然。这样做的复杂度为 O(m∑log⁡ci)O(m \sum \log c_i)。

不过这样做近似等于 O(nmlog⁡V)O(nm \log V)，有没有什么更快的方法呢？

有的兄弟，有的。回归朴素思想的转移式：

dpi,j=max⁡k=0ci(dpi−1,j−kwi+kvi)dp_{i,j}=\max_{k=0}^{c_i} (dp_{i-1,j-kw_i}+kv_i)

注意到，dpi,jdp_{i,j} 的有效转移 dpi−1,j−kwidp_{i-1,j-kw_i} 满足 j≡j−kwi(modci)j \equiv j-kw_i \pmod {c_i}，这启示我们把总容量 mm 拆成模 cic_i 同余类。此时，dpi,j′dp_{i,j'} 由 dpi,j′′,j′′∈[0,j′)dp_{i,j''}, j'' \in [0,j') 转移而来，可以使用单调队列优化。复杂度为 O(n∑ci∑mci)=O(nm)O(n\sum c_i \sum \dfrac{m}{c_i})=O(nm)。

P1776 宝物筛选

板子 +2。给出两种方法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 1e6 + 5;

int n, m, w[N], v[N], c[N];
int n1, w1[N], v1[N], dp[N];  // 拆完的

void _main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> c[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= c[i]; j <<= 1) w1[++n1] = w[i] * j, v1[n1] = v[i] * j, c[i] -= j;
		if (c[i]) w1[++n1] = w[i] * c[i], v1[n1] = v[i] * c[i];
	}
	for (int i = 1; i <= n1; i++) {
		for (int j = m; j >= w1[i]; j--) dp[j] = max(dp[j], dp[j - w1[i]] + v1[i]);
	}
	cout << dp[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 1e6 + 5;

int n, m, w[N], v[N], c[N];
int head, tail, q[N];
int dp[N], dp1[N]; // dp1用于暂存dp的值

void _main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> c[i];
	for (int i = 1; i <= n; i++) {
		memcpy(dp1, dp, sizeof(dp));
		for (int j = 0; j < w[i]; j++) {  
			head = tail = 0;
			for (int k = j; k <= m; k += w[i]) {
				if (head < tail && q[head] < k - w[i] * c[i]) head++;
				if (head < tail) dp[k] = max(dp1[k], dp1[q[head]] + (k - q[head]) / w[i] * v[i]);
				while (head < tail && dp1[k] >= dp1[q[tail - 1]] + (k - q[tail - 1]) / w[i] * v[i]) tail--;
				q[tail++] = k;
			}
		}
	}
	cout << dp[m];
}

P1782 旅行商的背包

前面是多重背包板子，后面注意到 m≤5m \le 5，直接枚举体积跑 01 背包，两种背包合并答案即可。

这怎么不算混合背包呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N = 1e5 + 5;

#define int long long
int n, m, w[N], v[N], c[N];
int n1, w1[N], v1[N], dp[N]; 
int nn, A[10], B[10], C[10];

void _main() {
	cin >> n >> nn >> m;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i] >> c[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= c[i]; j <<= 1) w1[++n1] = w[i] * j, v1[n1] = v[i] * j, c[i] -= j;
		if (c[i]) w1[++n1] = w[i] * c[i], v1[n1] = v[i] * c[i];
	}
	for (int i = 1; i <= n1; i++) {
		for (int j = m; j >= w1[i]; j--) dp[j] = max(dp[j], dp[j - w1[i]] + v1[i]);
	}
	
	for (int i = 1; i <= nn; i++) cin >> A[i] >> B[i] >> C[i];
	for (int i = 1; i <= nn; i++) {
		for (int j = m; j >= 1; j--) { 
			for (int k = 0; k <= j; k++) dp[j] = max(dp[j], dp[j - k] + A[i] * k * k + B[i] * k + C[i]);
		}
	}
	cout << dp[m];
}

P2347 [NOIP1996 提高组] 砝码称重

这是一道多重背包的可行性问题。事实上，背包可行性问题的判断适用 bitset 优化，且代码更为简单。

用 bitset<N> s 压位记录状态，第 ii 位表示 ii 能否取到，那么取 wiw_i 的值即为 s << w[i]，所以转移为 s |= s << w[i]。

1
2
3
4
5
6
7
8
9
10
11
12
const int N = 1005;
int a[8], w[8] = {1, 2, 3, 5, 10, 20};
bitset<N> s;

void _main() {
	for (int i = 0; i < 6; i++) cin >> a[i];
	s[0] = 1;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < a[i]; j++) s |= s << w[i];
	}
	cout << "Total=" << s.count() - 1;
}

分组背包

每种物品属于一个组，每组只能选一种。

思考一下与普通背包的差别，从所有物品中选变成从每组中选，所以对每组跑背包即可。复杂度多乘上一个组数。

P1757 通天之分组背包

板子 +3。更远古的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define N 1005
using namespace std;

namespace BackpackGroup {
	int s, n, w[N], v[N], g[N], cnt[N * N], f[N][N], dp[N];
	
	int backpack() {
		int y = *max_element(g + 1, g + n + 1);
		for (int i = 1; i <= n; i++) f[g[i]][++cnt[g[i]]] = i;
		for (int k = 1; k <= y; k++) {
			for (int j = s; j >= 0; j--) {
				for (int i = 1; i <= cnt[k]; i++) {
					int idx = f[k][i];
					if (j >= w[idx]) dp[j] = max(dp[j], dp[j - w[idx]] + v[idx]);
				}
			}
		}
		return dp[s];
	}
} 
using namespace BackpackGroup;  // 当时的逆天namespace马蜂

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> s >> n;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i] >> g[i];
	cout << backpack();
	return 0;
}

P5322 [BJOI2019] 排兵布阵

这题真正难的地方不是背包，而是转化。

把城堡看作物品，兵力看作体积，转换为背包模型。贪心地，对于每个城堡，若兵力 x>yx>y 且能打赢 xx，那就一定能打赢 yy。于是将输入的数组转置并排序。这时我们发现这已经被转化为分组背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 105;

int s, n, m, a[N][N], dp[20005];

void _main() {
	cin >> s >> n >> m;
	for (int i = 1; i <= s; i++) {
		for (int j = 1; j <= n; j++) cin >> a[j][i];
	}
	for (int i = 1; i <= n; i++) sort(a[i] + 1, a[i] + s + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= 0; j--) {
			for (int k = 1; k <= s; k++) {
				dp[j] = max(dp[j], j - 2 * a[i][k] - 1 < 0 ? 0 : dp[j - 2 * a[i][k] - 1] + k * i);
			}
		}
	}
	cout << dp[m];
}