【题目来源】
【题目描述】
自 01 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
【输入格式】
两个数 m,n，表示一共有 n 件物品，背包能承受的最大重量为 m。
接下来 n 行，每行 3 个数 ai,bi,ci，表示物品的重量，利用价值，所属组数。
【输出格式】
一个数，最大的利用价值。
【输入样例】
45 3
10 10 1
10 5 1
50 400 2
【输出样例】
10
【数据范围】
0≤m≤1000，1≤n≤1000，1≤k≤100，
ai，bi，ci 在 int 范围内。
【算法分析】
因为每组最多选择一个物品，所以可以将每组都看作一个整体，这就类似于 0/1 背包问题。
● 令 f[i][j] 表示将前 i 组物品放入容量为 j 的背包中可以获得的最大价值，vol[i][k] 表示第 i 组第 k 个物品的体积，val[i][k] 表示第 i 组第 k 个物品的价值，cnt[i] 表示第 i 组物品的个数，则分组背包问题的状态转移方程为：f[i][j]=max(f[i-1][j], f[i-1][j-vol[i][k]]+val[i][k]), j>=vol[i][k]
● 与 0/1 背包问题一样，可以对分组背包问题二维实现的状态转移方程进行一维数组优化，可得：
f[j]=max(f[j], f[j-vol[i][k]]+val[i][k])
其中，f[j] 表示将物品放入容量为 j 的背包中可以获得的最大价值。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int M=1e2+5;
const int N=1e3+5;
int vol[M][N],val[M][N],cnt[M];
int f[N];
int mx; //Maximum group number
int V,n,a,b,c;int main() {cin>>V>>n;for(int i=1; i<=n; i++) {cin>>a>>b>>c;cnt[c]++;vol[c][cnt[c]]=a;val[c][cnt[c]]=b;mx=max(mx,c);}for(int i=1; i<=mx; i++) {for(int j=V; j>=0; j--) {for(int k=1; k<=cnt[i]; k++) {if(j>=vol[i][k]) {f[j]=max(f[j],f[j-vol[i][k]]+val[i][k]);}}}}cout<<f[V]<<endl;return 0;
}/*
in:
45 3
10 10 1
10 5 1
50 400 2out:
10
*/
【参考文献】