【题意】
n件物品，背包可容纳重量为m的物品
每件物品有重量wi，价值vi，所属组别gi
同个组中的物品只能拿一件
问最大价值
【题解】
正常01背包的写法是
for i 枚举每个物品
for j 倒序枚举背包容量
f[j]=max(f[j], f[j-w[i]]+v[i])
在分组背包中，同个组中的物品互斥只能拿一件。 可以把每个组看成01背包的物品，“组”有多个重量和价值，可以从中任选一组(wi, vi) 来更新答案
那么写法可以改成
for i 枚举每个组
for j 倒序枚举背包容量
for k 枚举组内的物品
f[j]=max(f[j], f[j-w[k]]+v[k])
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 1010
using namespace std;
int n,m,k,f[N];
struct rec{
int weight, value;
};
vector<rec> object[N];
inline int read(){
int k=0,f=1; char c=getchar();
while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
return k*f;
}
int main(){
m=read(); n=read();
for(int i=1;i<=n;i++){
rec tmp;
tmp.weight=read();
tmp.value=read();
int group=read();
object[group].push_back(tmp);
k=max(k,group);
}
for(int i=1;i<=k;i++){
for(int j=m;j;j--){
for(vector<rec>::iterator it=object[i].begin(); it!=object[i].end(); it++){
if(j>=it->weight)
f[j]=max(f[j],f[j-it->weight]+it->value);
}
}
}
printf("%d\n",f[m]);
return 0;
}
原文：https://www.cnblogs.com/DriverLao/p/13056685.html