https://www.luogu.org/problemnew/show/P1064

分组背包，由于每组里的情况很少，只有5种，所以就不需要每组内部01背包过一遍了。只需要把主件附件放到一组里，像01背包那样，只是在每组里考虑所有的组合。考虑组合时也是需要考虑一下怎么写可以简化代码的。

#include<bits/stdc++.h>
using namespace std;

int V,n;
vector<int> c[65],w[65];
int d[32005];

void ZeroOnePack()
{
	for(int i=1;i<=n;i++)
	{
		if(c[i].size()==0)continue;
		for(int j=V;j>=0;j--)
		{
			if(c[i].size()>=1)
			{
				if(j>=c[i][0])d[j]=max(d[j],d[j-c[i][0]]+c[i][0]*w[i][0]);
	        }
	        if(c[i].size()>=2)
	        {
	        	if(j>=c[i][0]+c[i][1])d[j]=max(d[j],d[j-c[i][0]-c[i][1]]+c[i][0]*w[i][0]+c[i][1]*w[i][1]);
			}
			if(c[i].size()>=3)
			{
				if(j>=c[i][0]+c[i][1]+c[i][2])d[j]=max(d[j],d[j-c[i][0]-c[i][1]-c[i][2]]+c[i][0]*w[i][0]+c[i][1]*w[i][1]+c[i][2]*w[i][2]);
			}
		}
	}
}

int main()
{
	freopen("input.in","r",stdin);
	int v,p,q;
	cin>>v>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>v>>p>>q;
		if(q==0)c[i].push_back(v),w[i].push_back(p);
		else c[q].push_back(v),w[q].push_back(p);
	}
	
	ZeroOnePack();
	cout<<d[V]<<endl;
	return 0;
}