rqnoj 123 多人背包 K优解(不同策略相同权值视为不同)

缘起

【1】已经研究了01背包K优解的问题. 现在继续 rqnoj 123 多人背包

本题和【1】的区别在于本题 不同策略相同权值视为不同, 而 【1】是 不同策略相同权值视为相同。这就是《背包九讲2.0》 9.5 最后一个自然段讨论的两种情况

1
2
3
另外还要注意题目对于“第K优解”的定义，是要求将策略不同但权值相同
的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要
保证队列里的数没有重复的。

分析

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
题目描述
DD 和好朋友们要去爬山啦！他们一共有 K 个人，每个人都会背一个包。这些包的容量是相同的，都是 V。可以装
进背包里的一共有 N 种物品，每种物品都有给定的体积和价值。

在 DD 看来，合理的背包安排方案是这样的：

每个人背包里装的物品的总体积恰等于包的容量。

每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。

任意两个人，他们包里的物品清单不能完全相同。

在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？

输入格式
第一行有三个整数：K、V、N。(k<=50 v<=5000 n<=200 by RQ)

第二行开始的 N 行，每行有两个整数，分别代表这件物品的体积和价值。

输出格式
只需输出一个整数，即在满足以上要求的前提下所有物品的总价值的最大值。(最后有空行.)

样例输入
2 10 5
3 12
7 20
2 4
5 6
1 1

样例输出
57

首先, “每个包里的每种物品最多只有一件” 表明对每个背包而言是01背包. 而有K个背包, “任意两个背包，他们包里的物品清单不能完全相同。” 表明这是 “不同策略相同权值视为不同” 的01背包K优解问题。而 “每个人背包里装的物品的总体积恰等于包的容量。” 表明这是背包必须恰好装满的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
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 "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int inf = 0x3f3f3f3f, maxv = 5005, maxk = 55, maxn = 205;
int k,v,n, dp[maxv][maxk], a[maxn], b[maxn], tmp[maxk]; // a是体积, b是价值

void init() // dp 初始化（注意本题需要恰好装满）
{
    for (int i = 0;i<=v;i++)
	{
		for (int j = 0;j<k;j++)
		{
			dp[i][j] = -inf;
		}
	}
	dp[0][0] = 0; // 不选任何物品的话,只有容量为0的话, 排名最靠前的是0
}

void zo(int i) // 01背包, 归并两个k长度的非增队列
{
	for (int j = v,len,x,y; j>=a[i]; j--) // 归并 dp[j][0,..,k-1]和 dp[j-a[i]][0,...,k-1] 这两个非增队列
	{
		x = y = len =0;
		while(x<k && y<k && len<k)
		{
			if (dp[j][x]>dp[j-a[i]][y]+b[i])
			{
				tmp[len++] = dp[j][x++];
			}
			else
			{
				tmp[len++] = dp[j-a[i]][y++]+b[i];
			}
		}
		while(x<k && len<k)
		{
			tmp[len++] = dp[j][x++];
		}
		while(y<k && len<k)
		{
			tmp[len++] = dp[j-a[i]][y++]+b[i];
		}
		memcpy(dp[j], tmp, k*sizeof(int));
	} // 典型的归并
}

int main()
{
#ifdef LOCAL
	freopen("d:\data.in", "r", stdin);
//	freopen("d:\my.out", "w", stdout);
#endif
	scanf("%d%d%d", &k,&v,&n);
	for (int i = 1;i<=n;i++)
	{
		scanf("%d%d", a+i, b+i);
	}
	init();
	for (int i = 1;i<=n;i++)
	{
		zo(i);
	}
	int ans = 0;
	for (int i = 0;i<k;i++)
	{
		ans+=dp[v][i];
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

1
2
3
4
5
6
7
8
9
10
测试点1 Accepted / 1ms / 13644kB
测试点2 Accepted / 1ms / 13644kB
测试点3 Accepted / 11ms / 13644kB
测试点4 Accepted / 49ms / 13644kB
测试点5 Accepted / 138ms / 13644kB
测试点6 Accepted / 196ms / 13644kB
测试点7 Accepted / 228ms / 13644kB
测试点8 Accepted / 287ms / 13644kB
测试点9 Accepted / 300ms / 13644kB
测试点10 Accepted / 1ms / 13644kB

通过本题就知道了, 其实所谓背包K优解的问题就是将经典的背包的求max算子转换为归并队列而已

参考

【1】https://yfsyfs.github.io/2019/10/27/hdu-2639-Bone-Collector-II-01%E8%83%8C%E5%8C%85K%E4%BC%98%E8%A7%A3-%E4%B8%8D%E5%90%8C%E7%AD%96%E7%95%A5%E7%9B%B8%E5%90%8C%E6%9D%83%E5%80%BC%E8%A7%86%E4%B8%BA%E7%9B%B8%E5%90%8C/