hdu 1712 ACboy needs your help 分组背包

缘起

学习分组背包~ hdu 1712 ACboy needs your help

分析

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
现在acboy有m天的时间来修n门课程，然后给你一个矩阵，
A[i][j]表示花j天的时间学习第i门课程能够得到A[i][j]学分，
我们的任务是把acboy所拥有的天数m天分成一些部分来学习这其中的课程，使得能够在学校课程当中收获学分最多。

【输入】
多样例. 每个样例开始于 n和m, 然后是一个n*m矩阵.A[i][j], (1<=i<=N<=100,1<=j<=M<=100)
最后以两个0结尾

【输出】
对每个样例，输出最大收益

【样例输入】
2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0

【样例输出】
3
4
6

【限制】
1s

本题是经典的分组背包问题. 首先讲清楚分组背包问题

1
2
分组背包问题是N件物品,背包容量是V,第i件物品的重量是W[i],价值是P[i],这些物品分成K组
组内物品互斥,也就是不能共存于背包中(也就是每组物品中最多取一件),问背包的最大价值

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设F [k, v]表示前k组物品花费费用v能取得的最大权值，则有

1
F[k,v] = max{F[k-1, v], F[k-1,v-Ci]+Wi | item i 属于 group k}

使用伪代码写分组背包的算法模板也很简单

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}

之所以上面 for v = V,..,0, 能到0是因为一组物品完全可以不取任何一件. 分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。

回到本题分组背包就要找到互斥的物品才行. 然后将这些物品归为物品组.

本题的物品是 （共计m*n 件物品）

第1门课花费1天学,第1门课花费2天学,….,第1门课程花费m-1天学习, 第1门课程花费m天学习.

第2门课花费1天学,第2门课花费2天学,….,第2门课程花费m-1天学习, 第2门课程花费m天学习.

… …

第n-1门课花费1天学,第n-1门课花费2天学,….,第n-1门课程花费m-1天学习, 第n-1门课程花费m天学习.

第n门课花费1天学,第n门课花费2天学,….,第n门课程花费m-1天学习, 第n门课程花费m天学习.

而每行的m个物品归为一组, 而且互斥(即一门课程你决定使用x天学习就不能使用y天学习)，共计n组. 这样就是一个分组背包问题了. 然后背包容量显然就是天数——即你要从上面n个组中每组中至多选择一个物品, 使得消耗的天数总和<=m.

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 105;
int n,m, a[maxn][maxn], dp[maxn];

void gp() // 分组背包
{
	memset(dp,0,sizeof(dp)); // 不选任何一组, 则显然学分是0
	for (int k = 1; k<=n; k++) // 逐个考察前k组
	{
		for (int v = m; ~v; v--) // 背包容量为m, 用第k个物品组中的物品来进行01背包
		{
			for (int i = 1;i<=m;i++)
			{
				if (v>=i)
				{
					dp[v] = max(dp[v], dp[v-i]+a[k][i]); // 第k组的第i件物品消耗i(即决定花费i天学习第k门课程)
				}
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m), n||m)
	{
		for (int i = 1;i<=n; i++)
		{
			for (int j = 1;j<=m;j++)
			{
				scanf("%d", a[i]+j);
			}
		}
		gp();
		printf("%d\n", dp[m]); // 容量为m
	}
	return 0;
}

ac情况

Status Accepted
Time 93ms
Memory 1776kB
Length 738
Lang C++
Submitted 2019-10-25 17:54:19
Shared
RemoteRunId 31093222