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

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

dp[i][k] = max(max(dp[i][k], dp[i][k-x]+y), dp[i-1][k-x]+y);

```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 110;
vector <int> G[maxn];
int a[maxn], b[maxn], c[maxn];
int dp[maxn][maxn*maxn];

int main()
{

int n, m, t;
while(scanf("%d %d %d", &n, &m, &t) != EOF)
{
for(int i = 1; i <= t; i++)
G[i].clear();
for(int i = 1; i <= n; i++)
{
scanf("%d %d %d", &a[i], &b[i], &c[i]);
G[a[i]].push_back(i);
}
for(int i = 1; i <= t; i++)
for(int j = 0; j <= m; j++)
dp[i][j] = -999999999;
for(int i = 0; i <= m; i++)
dp[0][i] = 0;
for(int i = 1; i <= t; i++)
{
if(G[i].size() == 0)
break;
for(int j = 0; j < G[i].size(); j++)
{
int x = b[G[i][j]];
int y = c[G[i][j]];
for(int k = m; k >= x; k--)
{
dp[i][k] = max(max(dp[i][k], dp[i][k-x]+y), dp[i-1][k-x]+y);
}
}
}
if(dp[t][m] < 0)
puts("Impossible");
else
printf("%d\n", dp[t][m]);

}
return 0;
}
/*
3 5 3
1 2 5
2 2 1
3 2 2
*/
```