题意：有n种品牌的鞋子啊，每种品牌又分几类不同的鞋子。已知每双鞋子的标价和实际的价值。
要求每种品牌至少买一类鞋子。问花m钱能买的鞋子的最大价值。如果不能满足每种品牌至少
买一双鞋子（就是钱不够用啦)就输出不可能。
分析：
《背包九讲》中的分组背包是每组最多选一个。而这题是每组要至少选一个。
dp[i][k-v[j]]+w[j]表示不是第一次在本组中选鞋子。
dp[i-1][k-v[j]]+w[j]表示是第一次在本组中选，所以应该由上一组选择递推过来。
dp[i][j]表示前i中brand 用了j这么多的钱得到的价值。。。
初始化为负数。。。表示不能达到的状态（钱不够用）
另外dp[0][j]初始化为0，因为在第一类里选第一个时，如果钱够用是直接加上价值（初始量为0）。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int bnum,mon,tot;
int dp[15][10005];
int brand[105],w[105],v[105];
int maxx(int a,int b,int c)
{
int t=a>b?a:b;
return t>c?t:c;
}
void init()
{
for(int i=0;i<=bnum;i++)
{
for(int j=0;j<=mon;j++)
{
if(i==0)
dp[i][j]=0;
else
dp[i][j]=-INF;
}
}
}
void solve()
{
int i,j,k;
for(i=1;i<=bnum;i++)
{
for(j=1;j<=tot;j++)
{
if(brand[j]==i)
{
for(k=mon;k>=v[j];k--)
{
dp[i][k]=maxx(dp[i][k],dp[i][k-v[j]]+w[j],dp[i-1][k-v[j]]+w[j]);
}
}
}
}
}
int main()
{
while(scanf("%d%d%d",&tot,&mon,&bnum)!=EOF)
{
for(int i=1;i<=tot;i++)
scanf("%d%d%d",&brand[i],&v[i],&w[i]);
init();
solve();
if(dp[bnum][mon]<0)
printf("Impossible\n");
else
printf("%d\n",dp[bnum][mon]);
}
return 0;
}