【题意】
有S款运动鞋，一个n件，总钱数为m，求不超过总钱数且每款鞋子至少买一双的情况下，使价值最大。如果有一款买不到，就输出“Impossible"。
1<=N<=100 1 <= M<= 10000
【题解】
首先明显这是一个分组背包。
impossible 就直接看看每组最便宜的是否买得起。
因为每组最少选一个，所以我们可以这样dp：
f[k][j]表示当前扫到第k组，容量为j。
f[k][j]可由三个更新：
f[k][j]=f[k][j] 不选当前物品
f[k][j]=f[k-1][j-b[i]]+c[i] 选择当前物品，并且是在该组中第一次选物品
f[k][j]=f[k][j-b[i]]+c[i] 选择当前物品，并且不是在该组中第一次选
因为f[k][j]初始值为0，所以它最少都会买一样东西（由第二条更新得到）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std; const int N=,S=;
int n,m,K,a[N],b[N],c[N],mn[S],d[S][S],f[S][N]; int maxx(int x,int y){return x>y ? x:y;}
int minn(int x,int y){return x<y ? x:y;} int main()
{
freopen("a.in","r",stdin);
while(scanf("%d%d%d",&n,&m,&K)!=EOF)
{
memset(d,,sizeof(d));
memset(mn,,sizeof(mn));
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
d[a[i]][++d[a[i]][]]=i;
mn[a[i]]=minn(mn[a[i]],b[i]);
}
int x=;
for(int i=;i<=K;i++) x+=mn[i];
if(m<x) printf("Impossible\n");
else
{
memset(f,,sizeof(f));
for(int k=;k<=K;k++)
{
for(int i=;i<=d[k][];i++)
{
x=d[k][i];
for(int j=m;j>=b[x];j--)
{
f[k][j]=maxx(f[k][j],maxx(f[k-][j-b[x]]+c[x],f[k][j-b[x]]+c[x]));
}
}
}
printf("%d\n",f[K][m]);
}
}
return ;
}