可以将分组的背包看成若干个01背包来做。
#include<cstdio>
#include<iostream>
using namespace std;
int read(){
int num=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
num=num*10+c-'0';
c=getchar();
}
return num*f;
}
int n,m;
int v[65][3],p[65][3];
int cnt;
int f[32005];
int main(){
n=read(); m=read();
for(int i=1;i<=m;i++){
int vv=read(),pp=read(),qq=read();
if(qq==0){
v[i][0]=vv;
p[i][0]=pp*vv;
}
else if(!v[qq][1]){
v[qq][1]=vv;
p[qq][1]=pp*vv;
}
else{
v[qq][2]=vv;
p[qq][2]=pp*vv;
}
}
for(int i=1;i<=m;i++){
for(int j=n;j>=1;j--){
if(j-v[i][0]>=0){
f[j]=max(f[j],f[j-v[i][0]]+p[i][0]);
}
if(j-v[i][0]-v[i][1]>=0){
f[j]=max(f[j],f[j-v[i][0]-v[i][1]]+p[i][0]+p[i][1]);
}
if(j-v[i][0]-v[i][1]-v[i][2]>=0){
f[j]=max(f[j],f[j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]+p[i][1]+p[i][2]);
}
}
}
printf("%d",f[n]);
return 0;
}