部分背包

本文最后更新于：2022年8月25日 下午

UPD 2022.7.4：删除了 QQ 表情包（太智障了影响阅读者的心情）。一并删除了一些冗杂的话。

如果你实在是看不懂，那……要不回去复习复习基础的东西？

如果你没有 DP 基础，建议你去博文里边耐心地翻一翻我之前写过的 DP 入门——《什么是 DP》

无后效性

我们在写 DP 的时候，我们只需要记录结果就可以了，而不需要记录决策是什么，这个东西叫做无后效性。

这玩意在设计状态的时候比较重要，不然你的 DP 挂掉的几率……

背包

01 背包

来个例题：https://www.luogu.com.cn/problem/P1048。

这道题异常的经典，是背包的不二之选。

根据上一篇博文的传统思路，我们肯定得先设计状态。

比如我们设计这样一个状态：

1
用 dp[n] 表示用了前 n 个物品的最大价值。

这样的状态是会挂掉的，因为前 $n$ 个物品占据了空间，会导致你有可能无法接着放物品，有后效性。

1
用 dp[k] 表示用了 k 的空间的最大价值。

一样歇菜，你不知道前面的物品哪个用了哪个没用，还是不行。

那么怎么解决后效性的问题呢？

很简单，把产生后效性的东西扔进 $dp$ 里边就行了。

正确的状态：

1
dp[n][k] 表示用到前 n 个物品，占据了 k 的空间的最大价值。

然后根据我们之前的方法，推出方程：

$dp[n][k] = \max(dp[n-1][k], dp[n-1][k-v[i]] + w[i])$

然后直接开始写，没啥好说的。

欸不不不，还有一点：

最终的答案，是在 $dp[n][…]$ 里边选一个最大的。

然后，你应该可以自己写出来了吧？

大水题，剪贴板。

https://www.luogu.com.cn/paste/ohdv5old

再来一个：https://www.luogu.com.cn/problem/P1049。

这道题怎么办？

我们把它转化一下，既然求剩下的空间最小，我们就直接把能装下最多的空间用上面的方法求出来，然后用总空间一减就行。

这玩意又叫做：适配器原理。

适配器原理：

1
2
3
4
5
6
7
现在已知 A 问题的解决方式。

给你一个 B 问题。

你将它转换成 A 问题，用 A 问题的方式去求解。

最后，将输出换成 B 问题的。

过水，直接剪贴板。

https://www.luogu.com.cn/paste/4efph4qp

还有一个问题：https://www.luogu.com.cn/problem/P1060。

这种题无非就是换换 $w$ 的算法而已，我相信你们都能自己写出来。

什么你实在不行？

好吧，给你自己去看：

https://www.luogu.com.cn/paste/h4qikm3r

太水了，直接剪贴板待遇。

我们再来看看：

你是不是发现，那个 $n$，是不是只需要用一次？

以后每一次，是不是跟很久之前的 $n$ 一点关系都没有了？

那，我还存着你干什么，浪费空间让出题人卡爆我吗？

我们就要使用下一招：

滚动数组！

好了，怎么写呢？

挺简单，既然你只需要一层的，我新开个数组 $last$ 专门用来存上面的东西，然后再用个 #include <cstring> 里边的 memcpy 进行数组的复制就好了。

三个程序滚动数组版如下：

https://www.luogu.com.cn/paste/jsr0vj8e

太长了就直接扔剪贴板里边了，不过分吧？!

我们还可以采用另一种滚动数组的方法：原地滚动数组。

这一招就是换换循环顺序，然后你就可以直接过去了，连 $last$ 都不用开。

只放一个程序，不然我会累死。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 105
using namespace std;

int V, n;
int v[N], w[N];
int dp[1005];

int read() {
	int x = 0, w = 1;
	char c = 0;
	while(c < '0' || c > '9') {
		if(c == '-') {
			w = -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x*10+(c-'0');
		c = getchar();
	}
	
	return x * w;
}

void write(int x) {
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	if(x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

void inp() {
	V = read(), n = read();
	for(int i=1; i<=n; i++) {
		v[i] = read(), w[i] = read();
	}
}

void work() {
	for(int i=1; i<=n; i++) {
		for(int j=V; j>=0; j--) {
			if(j-v[i] >= 0) {
				dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
			}
		}
	}
	
	int ans = -1;
	for(int i=0; i<=V; i++) {
		ans = max(ans, dp[i]);
	}
	
	write(ans);
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	inp();
	work();
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

完全背包

换个问题：如果每个物品都可以取无限次，那怎么办？

https://www.luogu.com.cn/problem/P1616。

也好说，我直接告诉你一个 trick：

原地滚动数组，循环方式变成正着来，因为现在无限次取用允许你正着更新：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 10005
#define ll long long
using namespace std;

int V, n;
int v[N], w[N];
ll dp[10000005];

int read() {
	int x = 0, w = 1;
	char c = 0;
	while(c < '0' || c > '9') {
		if(c == '-') {
			w = -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x*10+(c-'0');
		c = getchar();
	}
	
	return x * w;
}

void write(ll x) {
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	if(x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

void inp() {
	V = read(), n = read();
	for(int i=1; i<=n; i++) {
		v[i] = read(), w[i] = read();
	}
}

void work() {
	for(int i=1; i<=n; i++) {
		for(int j=v[i]; j<=V; j++) {
			if(j-v[i] >= 0) {
				dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
			}
		}
	}
	
	ll ans = -1;
	for(int i=0; i<=V; i++) {
		ans = max(ans, dp[i]);
	}
	
	write(ans);
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	inp();
	work();
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

多重背包

https://www.luogu.com.cn/problem/P1776

现在第 $i$ 个物品只允许用 $a[i]$ 次，怎么办？

简单，叫出题人出来，武力解决。

简单点的思路：

弄出 $a[1]$ 个 1 号物品，$a[2]$ 个 2 号物品……

然后把它们统一地存在一个数组里边，用这个数组来跑 01 背包。

然后你会惊喜地发现，复杂度变成了 $(V * \sum{a[i]})$。

然后出题人跟你文斗，直接大数据送你 TLE，然后末影珍珠瞬移走，留下你一人抱着省二的证书痛哭失声。

那怎么办呢？

二进制分组！

问个问题：

1
[1, 2, 4, 5] 里面选一些数的和，是不是可以表示 12 以内所有的数？

proof：

[0, 7] 以内的数，肯定可以用 [1, 2, 4] 的子集和来表示，对吧？

[8, 12] 以内的数，先用个 5，接下来你要做的就是用 [1, 2, 4] 的子集和表示 [3, 7] 以内的数，这个问题刚才你已经解决过了。

把每种物品都分组，比如 14 个某物品可以分成 $[1, 2, 4, 7]$ 这些组。

分好这些组之后再扔给 01 背包去跑，直接输出结果。

物品总数就是：$\sum\log a[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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <algorithm>
#define N 1000005
using namespace std;

int n, m, ans;
int dp[N], w[N], v[N];
int pos = 1;

int read() {
	int x = 0, w = 1;
	char c = 0;
	while(c < '0' || c > '9') {
		if(c == '-') {
			w = -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x*10+(c-'0');
		c = getchar();
	}
	
	return x * w;
}

void write(int x) {
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	if(x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

void inp() {
	
	n = read(), m = read();
	for(int i=1; i<=n; i++) {
		int a = read(), b = read(), c = read();
		for(int j=1; j<=c; j<<=1) {
			v[++pos] = j * b, w[pos] = j * a;
			c-=j;
		}
		if(c) {
			v[++pos] = b * c, w[pos] = a * c;
		}
	}
}

void work() {
	for(int i=1; i<=pos; i++) {
		for(int j=m; j>=v[i]; j--) {
			dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
		}
	}
	
	write(dp[m]);
}

int main() {
	inp();
	work();
	return 0;
}

换换脑子，看个这个：

记忆化方法

还记得斐波那契数列吗？

$f(n) = f(n - 2) +f(n - 1)$

我们怎么去求呢？

来个比较暴力的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
using namespace std;

int fib(int n) {
	printf("call_fib(%d)\n", n);
	if(n <= 2) {
		return 1;
	}
	
	return fib(n - 2) + fib(n - 1);
}

int main() {
	printf("%d\n", fib(10));
	return 0;
}

这恐怖的调用次数……感觉随随便便我们就完蛋了，不是吗？

主要的问题是，无数的东西被重复调用了，这就很难受。

但是，有一种方法可以拯救我们：

记忆化！

具体来说就是开俩数组，一个用来看看有没有来过，另一个存储这个地方的值。

然后如果来过，直接返回值。

好了，进阶版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
using namespace std;

bool vis[1005];
int sum[1005];

int fib(int n) {
	if(vis[n]) {
		return sum[n];
	}
	
	printf("call_fib(%d)\n", n);
	if(n <= 2) {
		return 1;
	}
	
	vis[n] = true;
	return sum[n] = fib(n - 2) + fib(n - 1);
}

int main() {
	printf("%d\n", fib(10));
	return 0;
}

好了，看看这个题：https://www.luogu.com.cn/problem/P1541

如果你一看难度就被吓回去了……我建议你还是回来的好，别害怕嘛，这题很简单。

直接设计状态：

1
dp[pos][a][b][c][d] 表示走到 pos，用了 a 张 1，b 张 2，c 张 3，d 张 4

其中第一维可以滚掉，不然空间不行。

然后就简单了，你直接把所有牌扔进去，然后每次计算从 1 走到了哪里，加上答案，进行 dp，然后只要牌没打空就接着打。

代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <cstdio>
#include <algorithm>
#define N 355
#define M 45
using namespace std;

int sum[M][M][M][M];
bool vis[M][M][M][M];

int w[N], p[5], n, m;

int read() {
	int x = 0, w = 1;
	char c = 0;
	
	while(c < '0' || c > '9') {
		if(c == '-') {
			w = -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x*10+(c-'0');
		c = getchar();
	}
	
	return x * w;
}

void write(int x) {
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	if(x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

void inp() {
	n = read(), m = read();
	for(int i=1; i<=n; i++) {
		w[i] = read();
	}
	
	while(m--) {
		int x = read();
		p[x]++;
	}
}

int dp(int a, int b, int c, int d) {
	if(a == 0 && b == 0 && c == 0 && d == 0) {
		return w[1];
	}
	if(vis[a][b][c][d]) {
		return sum[a][b][c][d];
	}
	
	int pos = a + 2 * b + 3 * c + 4 * d;
	if(a) {
		sum[a][b][c][d] = max(sum[a][b][c][d], dp(a - 1, b, c, d));
	}
	if(b) {
		sum[a][b][c][d] = max(sum[a][b][c][d], dp(a, b - 1, c, d));
	}
	if(c) {
		sum[a][b][c][d] = max(sum[a][b][c][d], dp(a, b, c - 1, d));
	}
	if(d) {
		sum[a][b][c][d] = max(sum[a][b][c][d], dp(a, b, c, d - 1));
	}
	
	sum[a][b][c][d] += w[1+pos];
	vis[a][b][c][d] = true;
	
	return sum[a][b][c][d];
}

void work() {
	write(dp(p[1], p[2], p[3], p[4]));
}

int main() {
//	freopen("P1541.in", "r", stdin);
//	freopen("P1541.out", "w", stdout);
	inp();
	work();
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
OI
#Algorithm
部分背包
http://dxrprime.github.io/2022/08/25/无后效性，记忆化，滚动数组，简单背包/
作者
Shelter Prime
发布于
2022年8月25日
许可协议