解题报告&学习笔记：luogu P1757

题目链接：P1757 通天之分组背包
不知道吧，我背包还没学完呢
分组背包板子题。
我们可以把一个组看成一个大的物品，进行 (01) 背包。
对于一个组别的内部，我们一一枚举找到最优的物品，为了保证只选一个，我们对于每一个容量枚举每个物品，而非对于每个物品，枚举每个容量（这样就成了在这一组中进行 (01) 背包了。）
保证只选一次，循环还是倒序的。
时间复杂度仍然是 (mathcal O(nm))，可以通过本题。

(Code):

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define read(x) scanf("%d",&x)

int n,m;
struct node
{
	int v,w,c;
}a[1005];
int siz[1005],be[1005];
int cnt=0;
int dp[1005]={0};

bool cmp(node x,node y){return x.c<y.c;}

int main()
{
	read(m),read(n);
	for(int i=1;i<=n;i++) read(a[i].v),read(a[i].w),read(a[i].c);
	sort(a+1,a+n+1,cmp);
	int last=-1;
	for(int i=1;i<=n;i++)
	{
		if(a[i].c!=last) siz[++cnt]++,be[cnt]=i,last=a[i].c;
		else siz[cnt]++;
	}
        //be[]数组代表每个组别第一个物品的编号，便于下边枚举
	for(int i=1;i<=cnt;i++)
	{
		for(int j=m;j>=0;j--)
		{
			for(int k=1;k<=siz[i];k++)
			{
				int s=be[i]+k-1;
				if(a[s].v>j) continue;
				dp[j]=max(dp[j],dp[j-a[s].v]+a[s].w);
			}
		}
	}
	printf("%d
",dp[m]);
	return 0;
}