一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
Description
Input
第一行：三个整数，V(背包容量，V<=200)，N(物品数量，N<=30)和T(最大组号，T<=10)；
第2..N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。
Output
输出一个数，表示最大总价值。
Sample Input
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
Sample Output
20
【分析】分组背包，顾名思义就是一些物品被分组了，每组中只能拿一个或者不拿，最后求最大价值，这个就要多遍历一层，即每组成员，将前i-1组获得的最大价值与加上第i-1组每个物品后的价值比较，更新最大值，最后dp[m]就是最大价值。
【代码】
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=35;
int main()
{int m,n,t;int v[N],value[N],num[N][N],dp[205];while(~scanf("%d%d%d",&m,&n,&t)){memset(dp,0,sizeof(dp));//记得清零memset(num,0,sizeof(num));memset(v,0,sizeof(v));memset(value,0,sizeof(value));for(int i=1;i<=n;++i){int p;scanf("%d%d%d",&v[i],&value[i],&p);num[p][++num[p][0]]=i;//这一步很巧妙，保存每组的成员编号}for(int i=1;i<=n;++i)for(int j=m;j>=0;--j)//空间更新for(int k=1;k<=num[i][0];++k)//遍历每组所有成员if(v[num[i][k]]<=j)//判断如果i组当前成员重量小于等于背包剩余重量 就更新背包价值最大值dp[j]=max(dp[j],dp[j-v[num[i][k]]]+value[num[i][k]]);printf("%d\n",dp[m]);}return 0;
}