有k类物品 至少每种选一个 求最大价值
考虑只有一类物品 那么就是01背包了 现在k类 那就多加一维好了
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
*/
HDU 3033 I love sneakers! / 分组背包,布布扣,bubuko.com
HDU 3033 I love sneakers! / 分组背包
原文：http://blog.csdn.net/u011686226/article/details/21609591