思路分析：
如果看了好多解题报告还不懂思路的话，请自己copy一份解题报告，然后在更新dp数组的前后，输出一个dp数组就可以啦~
dp【i】【j】表示前i种鞋子 j容量下的背包最多能装多少
首先要将那些永远不会到达的状态标记为-1，
也就比如说，你买第一种产品的时候，那些钱不够的状态。那么后面就更不用考虑这些状态了，因为他第一种鞋子都没买到，就更不用谈买第二种。
然后把dp【1】【1-M】标记为0 开始递推。
if(dp[t-1][j-w[index]]!=-1)
dp[t][j]=max(dp[t][j],dp[t-1][j-w[index]]+v[index]); 代表这个种类是第一次选。
if(dp[t][j-w[index]]!=-1)
dp[t][j]=max(dp[t][j],dp[t][j-w[index]]+v[index]); 代表这个种类不是第一次选。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int dp[12][10005];
vector <int> S[105];
int w[105];
int v[105];
int main()
{
int n,W,type;
while(scanf("%d%d%d",&n,&W,&type)!=EOF)
{
for(int i=1;i<=type;i++)
S[i].clear();
for(int i=1;i<=n;i++)
{
int tmp;
scanf("%d%d%d",&tmp,&w[i],&v[i]);
S[tmp].push_back(i);
}
for(int i=0;i<=type;i++)
{
for(int j=0;j<=W;j++)
{
//printf("j = %d\n",j);
if(i==0)dp[i][j]=0;
else dp[i][j]=-1;
}
}
for(int t=1;t<=type;t++)
{
for(int i=0;i<S[t].size();i++)
{
int index=S[t][i];
for(int j=W;j>=w[index];j--)
{
if(dp[t][j-w[index]]!=-1)
dp[t][j]=max(dp[t][j],dp[t][j-w[index]]+v[index]);
if(dp[t-1][j-w[index]]!=-1)
dp[t][j]=max(dp[t][j],dp[t-1][j-w[index]]+v[index]);
}
}
}
if(dp[type][W]<0)
printf("Impossible\n");
else printf("%d\n",dp[type][W]);
}
return 0;
}
/*
3 5 3
1 2 5
2 2 1
3 2 2
Impossible
*/