hdu 3033 I love sneakers! 分组背包 每组至少选1件

缘起

学习分组背包, 【1】中展示了分组背包的板子. 那里对分组背包的定义是每个物品组中至多选择一件商品. 现在将分组背包问题的定义稍微改动一下

1
2
分组背包问题是N件物品,背包容量是V,第i件物品的重量是W[i],价值是P[i],这些物品分成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
有n双鞋子，m块钱，k个品牌，（一个品牌可以有多种价值不同的鞋子），
接下来n双不同的鞋子，a为所属品牌，b为要花费的钱，c为所能得到的价值。
有个人有个伟大的梦想，每个品牌的鞋子至少买一双，
问他这个梦想可以实现不？不可以实现输出Impossible，可以实现输出最大价值.

【输入】
多样例. 每个样例开始于一个n(1<=n<=100), 1 <= m<= 10000, 1<=k<=10
然后n行每行1<=a<=k, b , c, 三个整数, 0<=b,c<100000,分别表示它属于哪个品牌, 价格,在某人心目中的
价值

【输出】
对每个样例，输出最大价值或者 Impossible

【样例输入】
5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66

【样例输出】
255

【限制】
1s

咋一眼看过去, 就是个裸的分组背包问题, 但是和经典的分组背包板子不同之处在于要求每个物品组中的物品至少取一件. 所以再次应验了那句话——死套背包板子是没有出路的~ 灵活运用才是王道~

回顾一下【1】中分组背包板子

1
2
3
4
5
def function gp:
for k = 1...K
	for v = V,..,0
		for	item i in group k
			F[v] = max{F[v], F[v-Ci]+Wi}

我们思考为什么上面的板子保证了每组物品至多取一个? 只有把这个问题思考清楚了, 才知道怎么变换一下保证每组物品至少取一个. 答案就是先对v循环, 然后对固定的v, 再对物品进行循环, 求出F[v], 因为v是倒序遍历的, 所以保证了计算F[v]的时候用到的数据都是k-1时候得到的数据.

那么对于本题而言, 怎么做呢? 死套背包模板还是没有出路的! 首先 impossible是好判断的——只需要将每组的最小价格加起来, 如果仍然超出m的话,肯定impossible. 否则的话, 就一定不会impossible.

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
令dp[i][j] 是前i个物品组中每组都至少取一件而且容量限制为j的最大值. 则初始化为
dp[0][j] = 0, 
dp[others][others]=-1, 其中-1表示非法状态.
则dp[i][j]的转移方程怎么写呢? 
其实转移方程不就是要考虑dp[i][j]表述的状态能由哪些状态转移来吗?
显然可以从 dp[i][j-第i个物品组中的某个物品(假设是第i个物品组的第k件物品)的耗费(下面记做Aik)]
转移过来,当然, 前提是dp[i][j-Aik]不能等于-1, 即必须是从合法状态转移过来才行
也可以从dp[i-1][j-Aik]转移过来, 当然, 前提也是 dp[i-1][j-Aik]!=-1
所以我们有如下dp方程

if(j>=Aik && ~dp[i][j-Aik])
{
	dp[i][j] = max(dp[i][j], dp[i][j-Aik]+Bik); // Bik是第i个物品组的第k件物品的价值
}

if(j>=Aik && ~dp[i-1][j-Aik])
{
	dp[i][j] = max(dp[i][j], dp[i-1][j-Aik]+Bik); 
}

注意,上面两个if的过程是不能交换顺序的. 因为第一个if其实是用"前i组已经满足每组至少选择一个(假设已经选择的物品是S),然后第i组再
选一个（假设选择的物品是T）"这种情形来max化dp[i][j], 注意,因为物品是遍历的（组内物品的遍历顺序显然无所谓）, 所以S和T显然不是同一件物品.
第二个if其实是用"前i-1组已经满足每组至少选择一个, 但是第i组现在选择第一件物品" 来max化dp[i][j]
那么如果第二个if跑到第一个if前面去, 则就会重复选择一件物品. 反之就不会.
这里多说一句, 因为每个物品至多只能选择一次,所以j显然要从V倒向遍历（这一点和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
//#include "stdafx.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 105, maxm = 10005, maxk =15;
int n,m,k,a[maxn],b[maxn],c[maxn],dp[maxn][maxm],mmin[maxk];
vector<int> g[maxk];
typedef vector<int>::iterator vit;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d%d", &n,&m,&k))
	{
		for (int i = 1;i<=k;i++)
		{
			g[i].clear();
		}
		memset(dp, 0, sizeof(dp));
		memset(mmin,0x3f,sizeof(mmin));
		for (int i = 1;i<=n;i++)
		{
			scanf("%d%d%d", a+i,b+i,c+i);
			mmin[a[i]] = min(mmin[a[i]], b[i]);
			g[a[i]].push_back(i);
		}
		int s = 0;
		for (int i = 1;i<=k; i++)
		{
			s+=mmin[i];
		}
		if (s>m)
		{
			puts("Impossible");
			continue;
		} // 显然Impossible的充要条件就是各个品牌的最低价之和仍旧>钱数m
		memset(dp,-1,sizeof(dp));
		for (int i = 0;i<=m;i++)
		{
			dp[0][i] = 0;
		} // dp初始化
		for (int i = 1;i<=k;i++) // 遍历每个物品组
		{
			for (vit x = g[i].begin(); x!=g[i].end(); x++) // 遍历物品组中每个物品
			{
				for (int v = m;v>=b[*x]; v--) // 因为要保证每件物品至多选择一次, 所以v是倒向遍历的(这一点和01背包一样)
				{
					if (~dp[i][v-b[*x]])
					{
						dp[i][v] = max(dp[i][v], dp[i][v-b[*x]]+c[*x]);
					} // 优先从本层转移过来
					if (~dp[i-1][v-b[*x]])
					{
						dp[i][v] = max(dp[i][v], dp[i-1][v-b[*x]]+c[*x]);
					} // 从上一层转移过来
				}
			}
		}
		printf("%d\n", dp[k][m]);
	}
	return 0;
}

ac情况

Status Accepted
Time 140ms
Memory 5860kB
Length 1390
Lang C++
Submitted 2019-10-26 20:30:52
Shared
RemoteRunId 31121298

参考

【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/