題意：看樣例：
5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66
第一行 中 5 代表 有5個 物品，（以下有5行，即每個物品信息），10000代表現在的錢數（即背包體積），3代表物品分3個品牌，以下有5行，每行第一個數
為 品牌，第二個 為 花費錢數（即占用體積），第三個為 獲得的 價值。
滿足一下條件：1：每個物品最多能拿一次（即01背包） 2：每個品牌的物品至少拿一個！！
求滿足條件的 最大價值！！若無 輸出
Impossible 。
思路：這個分組背包和我們常見的 分組背包（每組最多拿1個）有很大區別。但是代碼只需要
把3層循環的順序 改變一下，初始化改變一下 即可。。具體的自己比較代碼、、
AC代碼：
[cpp]
/*分組背包*/
#include<stdio.h>
#include<string.h>
int dp[20][10050];
struct hi
{
int x;
int y;
}w[20][200];
int max(int a,int b)
{
if(a<b) a=b;
return a;
}
int main()
{
int a,b,c,n,m,v;
while(~scanf("%d%d%d",&n,&v,&m))
{
int g[20]={0};
for(a=0;a<n;a++)
{
scanf("%d",&b);
scanf("%d%d",&w[b][g[b]].x,&w[b][g[b]].y);
g[b]++; www.2cto.com
}
/*for(a=1;a<=m;a++)
{ for(b=0;b<g[a];b++)
{
printf("-->%d %d",w[a][b].x,w[a][b].y);
}
printf("\n");}*/
memset(dp,-9999,sizeof(dp));
dp[0][0]=0;
for(a=1;a<=m;a++)
{
for(b=0;b<g[a];b++)
{
for(c=v;c>=w[a][b].x;c--)
{
dp[a][c]=max(dp[a][c],max(dp[a-1][c-w[a][b].x]+w[a][b].y,dp[a][c-w[a][b].x]+w[a][b].y));
}
}
}
int ans=0;
for(a=0;a<=v;a++)
if(ans<dp[m][a])
ans=dp[m][a];
if(ans!=0)
printf("%d\n",ans);
else
puts("Impossible");
}
}
