题意：有n双鞋子，m块钱，k个品牌，（一个品牌可以有多种价值不同的鞋子），接下来n种不同的鞋子，a为所属品牌，b为要花费的钱，c为所能得到的价值。每种价值的鞋子只会买一双，有个人有个伟大的梦想，每个品牌的鞋子至少买一双，问他这个梦想可以实现不？不可以实现输出Impossible，可以实现输出最大价值......
思路：很容易看出来这是个分组背包题，当然这个分组背包有些不同于每组最多取一个的分组背包......但我是觉得，分组背包就这么几种问法吧
1、最常见的、最水的，每组最多取1个.........（一般是隐性的，需要自己分析）
2、每组至少取1个........（就是本题）
3、随意选，可以选，可以不选，可以只选1个，也可以选多个......（暂时还未学，马上会学）.....
对于第一种，模板题，只要你可以分析出来，那么可以水过.....
对于第二种，我想说也是模板题，当然是以本题为基础的模板.........
好吧，这道题目，首先，每组至少取一个，就是说必须要取一个，那么数组dp[i][j]，代表的含义就是 前i组容量为j的情况下所得到的最大价值为dpi][j]；
同样的，我们首先思考它的状态，每组必须要取一个，那么第i组存在的情况下，第i-1组也必须存在，也是回到了前面所做背包所说的那种“一定”、“必须”的状态，那么同样的在动态转移的时候，要判断它的前一个状态合不合法，我个人比较喜欢用0来判断不合法，>0判断合法.......初始化dp[0][0]=1，最后得到的结果减去1......我想说的是，最后的结果不一定会集中在dp[k][m]上，因为这个状态它不一定存在，也就是说，这个状态不一定合法，当然，也没有关系，我们考虑第k组一定要存在，那么扫描下dp[k][i]，取最大值就好.....
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int dp[15][10005],s[105][2],num[15][105];
queue<int>Q[105];
int main()
{
int n,m,k;
while(scanf("%d %d %d",&n,&m,&k)>0)
{
for(int i=0;i<105;i++)
while(!Q[i].empty())
Q[i].pop();
for(int i=1;i<=n;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
Q[a].push(i);
s[i][0]=b;
s[i][1]=c;
}
for(int i=1;i<=k;i++)
{
int j=1;
while(!Q[i].empty())
{
num[i][j++]=Q[i].front();
//printf("i==%d %d
",i,Q[i].front());
Q[i].pop();
}
num[i][0]=j;
} //前面都是将数据处理好
memset(dp,0,sizeof(dp)); //初始化dp
dp[0][0]=1;
int flag=1;
for(int i=1;i<=k;i++) //这是分组
{
if(num[i][0]==1) //要是有一组没有数据，那么说明，它不可能满足每组必须取一个这条件.......
{
flag=0;
break;
}
for(int f=1;f<num[i][0];f++) //不同于最多取一个的分组背包，这里是先放每组有的物品，后放容积.......
{
int xx=num[i][f];;
for(int j=m;j>=0;j--) //至于为什么这么放？我是认为，它是一种模板.......
{
if(j-s[xx][0]>=0&&dp[i][j-s[xx][0]]&&dp[i][j-s[xx][0]]+s[xx][1]>dp[i][j]) //这个判断必须放到第一，以免重复
dp[i][j]=dp[i][j-s[xx][0]]+s[xx][1];
if(j-s[xx][0]>=0&&dp[i-1][j-s[xx][0]]&&dp[i-1][j-s[xx][0]]+s[xx][1]>dp[i][j])//这个必须放在上一个判断下面.....
dp[i][j]=dp[i-1][j-s[xx][0]]+s[xx][1];
}
}
}
int maxx=0;
for(int i=0;i<=m;i++)
if(maxx<dp[k][i])
maxx=dp[k][i];
if(maxx==0||flag==0)
printf("Impossible
");
else
printf("%d
",maxx-1);//最大值记得减去1
}
return 0;
}