hdu 3033 I love sneakers! 分组背包

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int d[12][11000],cnt[11],c[12][110],w[12][110];

int main()
{
    int kk,n,m;
    while(~scanf("%d%d%d",&n,&m,&kk))
    {
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)
        {
            int k;
            scanf("%d",&k);
            scanf("%d%d",&c[k][cnt[k]],&w[k][cnt[k]]);
            cnt[k]++;
        }
        memset(d,-1,sizeof(d));
        memset(d[0],0,sizeof(d[0]));
        for(int k=1;k<=kk;k++)
            for(int i=0;i<cnt[k];i++)
                for(int j=m;j>=c[k][i];j--)
                {
                    if(d[k][j-c[k][i]]!=-1)
                        d[k][j]=max(d[k][j],d[k][j-c[k][i]]+w[k][i]);
                    if(d[k-1][j-c[k][i]]!=-1)
                        d[k][j]=max(d[k][j],d[k-1][j-c[k][i]]+w[k][i]);
                }
        if(d[kk][m]==-1) cout<<"Impossible"<<endl;
            else    cout<<d[kk][m]<<endl;
    }
}