这题的动态转移方程真是妙啊，完美的解决了每一种衣服必须买一件的情况。
if(a[x][i-c[x][j].x]!=-1) a[x][i]=max(a[x][i],a[x][i-c[x][j].x]+c[x][j].y);
if(a[x-1][i-c[x][j].x]!=-1) a[x][i]=max(a[x][i],a[x-1][i-c[x][j].x]+c[x][j].y);
第一个if里的条件是如果该种物品已经被选，那么，就按照一般的背包问题讨论
第二个if里的条件是如果上一种的物品被选，那么，就按照一般的背包问题讨论
有了这两个if，就可以保证dp得出的值是一定满足条件的。当然，如果无法得出，那么最后的答案就会是初始值-1
代码如下：
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
struct dd
{
int x;int y;
}s;
vector<dd> c[15];
int main()
{
long long a[15][10009],n,m,i,x,k,y,j,z;//maxx=0;
while(cin>>n>>m>>k)
{
memset(a,-1,sizeof(a));
memset(a[0],0,sizeof(a[0]));
for(i=1;i<=k;i++) c[i].clear();
for(i=1;i<=n;i++)
{
cin>>x>>s.x>>s.y;
c[x].push_back(s);
//maxx+=b[i];
}
for(x=1;x<=k;x++)
{
for(j=0;j<c[x].size();j++)
{
for(i=m;i>=c[x][j].x;i--)
{
if(a[x][i-c[x][j].x]!=-1) a[x][i]=max(a[x][i],a[x][i-c[x][j].x]+c[x][j].y);
if(a[x-1][i-c[x][j].x]!=-1) a[x][i]=max(a[x][i],a[x-1][i-c[x][j].x]+c[x][j].y);
}
}
}
if(a[k][m]==-1) cout<<"Impossible"<<endl;
else cout<<a[k][m]<<endl;
}
}