Fork me on GitHub

题解 P1757【通天之分组背包】

发表于 | 分类于 |

这是一道分组背包的裸板子题啊qwq，今天小蒟蒻来给大家讲一下分组背包的简单使用方法（毕竟难的也不会啊TAT（逃

首先看一下题目

题目背景
直达通天路·小A历险记第二篇

题目描述
自01背包问世之后，小A对此深感兴趣。一天，小A去远游，却发现他的背包不同于01背包，他的物品大致可分为k组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入输出格式
输入格式：
两个数m,n，表示一共有n件物品，总重量为m

接下来n行，每行3个数ai,bi,ci，表示物品的重量，利用价值，所属组数

输出格式：
一个数，最大的利用价值

输入输出样例
输入样例#1： 复制
45 3
10 10 1
10 5 1
50 400 2
输出样例#1： 复制
10
说明
1<=m<=1000 1<=n<=1000 组数t<=100

首先我们用一个数组w[i]来保存每个物品的重量，c[i]表示每个物品的价值，定义二维数组a[p][0]表示第p组的物品有a[p][0]件，里面存储这个物品的序号为[i]，定义一个变量t来保存一共有多少组物品。

那么这个题的状态转移方程就变得非常简单啦，大致类似于01背包，注意控制循环变量的时候把组数放在外面（或许只有本蒟蒻犯了这种zz的错误QAQ

下面状态转移方程和循环变量就在代码里啦qwq

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int w[10001],t,c[10001],v,f[10001],a[10001][1001],m,n,p;

int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d%d%d",&w[i],&c[i],&p);
		a[p][++a[p][0]]=i;
		t=max(t,p);
	}
	for(int k=1; k<=t; k++)//控制组数
		for(int j=m; j>=0; j--)//容量
			for(int i=1; i<=a[k][0]; i++)//枚举
				if(w[a[k][i]]<=j)//先判断能不能放
					f[j]=max(f[j],f[j-w[a[k][i]]]+c[a[k][i]]);
	printf("%d",f[m]);
}
召唤蕾姆