hdu 3535 AreYouBusy 分组背包+至少选1+至多选1+随意

缘起

关于分组背包, 【1】中我们做了标准的分组背包问题, 【2】中我们做了分组背包的变式——每组至少取一个物品. 现在将这两者杂糅在一起~ hdu 3535 AreYouBusy

分析

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
n个工作集, t时间, 每个工作集有不同的属性s, s=0表示这个工作集至少选一件来做, s=1表示至多选一件来做
s=2表示随意. 每件工作都有占用时间以及获取的价值. 问如何选择使得获取的价值最大?

【输入】
多样例. 每个样例以n和T开始.(0<=n,T<=100) 然后是n组描述. 每组开始于2个整数m, s,(0<m<=100)
其中m是该组工作集中工作的件数. 然后是m行, 每行 ci gi(0<=ci,gi<=100),表示此项工作耗费的时间
和攫取的价值,注意,每件工作至多只能做一次.

【输出】
对每个样例,输出最大价值。如果无法完成, 输出-1

【样例输入】
3 3
2 1
2 5
3 8
2 0
1 0
2 1
3 2
4 3
2 1
1 1

3 4
2 1
2 5
3 8
2 0
1 1
2 8
3 2
4 4
2 1
1 1

1 1
1 0
2 1

5 3
2 0
1 0
2 1
2 0
2 2
1 1
2 0
3 2
2 1
2 1
1 5
2 8
3 2
3 8
4 9
5 10

【样例输出】
5
13
-1
-1

【限制】
1s

首先遍历物品组, 对于s=0的物品组, 施展【2】中的方法, 对于s=1的物品组,施展【1】中的标准分组背包的板子, 对于s=2的情况, 只需要对每件物品跑标准的01背包就行了. 和【2】一样, 令 dp[i][j] 是前i个物品组, 满足s属性条件下容量<=j的最大背包值（鉴于要使用【2】所以dp必须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
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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 105;
int n,t,m,s,dp[maxn][maxn],c[maxn], g[maxn];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d", &n,&t))
	{
		memset(dp,0,sizeof(dp)); // 考虑到有s=1,2,所以不能像【2】那般置为-1
		for (int i = 1;i<=n;i++)
		{
			scanf("%d%d", &m,&s);
			for (int j= 1;j<=m;j++)
			{
				scanf("%d%d", c+j,g+j);
			}
			switch(s)
			{
			case 0:
				memset(dp[i],-1,sizeof(dp[i])); // 和【2】一样,将本层状态置为非法状态
				for (int j = 1;j<=m;j++)
				{
					for (int v = t;v>=c[j];v--)
					{
						if (~dp[i][v-c[j]])
						{
							dp[i][v] = max(dp[i][v], dp[i][v-c[j]]+g[j]);
						}
						if (~dp[i-1][v-c[j]])
						{
							dp[i][v] = max(dp[i][v], dp[i-1][v-c[j]]+g[j]);
						}
					}
				}
				break;
			case 1:
				memcpy(dp[i], dp[i-1], sizeof(dp[i])); // 本物品组至多选一件, 所以是标准分组背包,这没问题,问题的关键在于初始值,dp[i]的初始值应该是dp[i-1], 因为我完全可以本物品组一件都不选
				for (int v = t;~v;v--)
				{
					for (int j = 1;j<=m;j++)
					{
						if (v>=c[j] && ~dp[i-1][v-c[j]]) // 本物品组的状态只能从上个物品组的（合法）状态转移过来
						{
							dp[i][v] = max(dp[i][v], dp[i-1][v-c[j]]+g[j]);
						}
					}
				}
				break;
			case 2:
				memcpy(dp[i], dp[i-1], sizeof(dp[i])); // 本组物品的初始值来自于上一层(因为本物品组我完全可以一件都不选)
				for (int j =1;j<=m;j++)
				{
					for (int v = t; v>=c[j]; v--) // 本组物品中对每一件做单纯的01背包就行了(注意,这里的dp[i][v]就相当于是滚动数组优化之后的dp[v],因为这里的i并不是物品,而是物品组),即保证本物品组中每一件至多选一次就行了
					{
						if (~dp[i][v-c[j]])
						{
							dp[i][v] = max(dp[i][v], dp[i][v-c[j]]+g[j]);
						}
					}
				}
				break;
			default:
				break;
			}
		}
		printf("%d\n", dp[n][t]);
	}
	return 0;
}

ac情况

Status Accepted
Time 46ms
Memory 1784kB
Length 1708
Lang C++
Submitted 2019-10-27 08:20:27
Shared
RemoteRunId 31125995

参考

【1】https://yfsyfs.github.io/2019/10/25/hdu-1712-ACboy-needs-your-help-%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85/

【2】https://yfsyfs.github.io/2019/10/26/hdu-3033-I-love-sneakers-%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85-%E6%AF%8F%E7%BB%84%E8%87%B3%E5%B0%91%E9%80%891%E4%BB%B6/