# HDU 3033 I love sneakers! 分组双肩包

www.MyException.Cn  网友分享于：2014-05-05  浏览：0次
HDU 3033 I love sneakers! 分组背包

```#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <map>

#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long LL
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 1000000007
#define LM(a,b) (((ULL)(a))<<(b))
#define RM(a,b) (((ULL)(a))>>(b))

using namespace std;

int Top[12];

struct N
{
int c,w;
}pro[12][110];

int dp[12][10011];

int main()
{
int n,m,k;

int u,v,w,i,j;

while(scanf("%d %d %d",&n,&m,&k) != EOF)
{
memset(dp,-1,sizeof(dp));

memset(Top,0,sizeof(Top));

for(i = 0; i < n; ++i)
{
scanf("%d %d %d",&u,&v,&w);
pro[u][Top[u]].c = v;
pro[u][Top[u]].w = w;
Top[u]++;
}

dp[0][0] = 0;

for(i = 1;i <= k; ++i)
{
for(j = 0;j < Top[i]; ++j)
{
for(w = m-pro[i][j].c; w >= 0; w--)
{
if(dp[i][w] != -1 && dp[i][w+pro[i][j].c] < dp[i][w] + pro[i][j].w)
{
dp[i][w+pro[i][j].c] = dp[i][w] + pro[i][j].w;
}

if(dp[i-1][w] != -1 && dp[i][w+pro[i][j].c] < dp[i-1][w] + pro[i][j].w)
{
dp[i][w+pro[i][j].c] = dp[i-1][w] + pro[i][j].w;
}
}
}
}
int Max = dp[k][0];

for(i = 1;i <= m; ++i)
{
Max = max(Max,dp[k][i]);
}

if(Max == -1)
{
printf("Impossible\n");
}
else
{
printf("%d\n",Max);
}
}

return 0;
}

```