题意：
有n件物品，对应有不同的价格和价值，这是典型的01背包。但现在有了一个限制，要买物品先买能装这件物品的特定的盒子，盒子的价值为0
代码理解得还不是太好，感觉这是一个“二重”的01背包。首先假设先买第i个盒子，对每个盒子里的物品进行一次01背包；然后对盒子再进行一次01背包，决策到底要不要买这个盒子
dp[i][j]表示前i个盒子有j元钱能获得的最大价值，则所求就是dp[n][total]
因为物品对盒子有了“依赖”，所以要先对dp赋值为-1，表示买不到盒子就更不可能装物品
这篇题解写的很详细：
http://www.acmerblog.com/hdu-3449-consumer-5475.html
代码虽短，还须多多体会
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = + ;
int dp[][maxn]; int main(void)
{
#ifdef LOCAL
freopen("3449in.txt", "r", stdin);
#endif int n, total;
while(scanf("%d%d", &n, &total) == )
{
memset(dp, -, sizeof(dp));
memset(dp[], , sizeof(dp[]));
for(int i = ; i <= n; ++i)
{
int box, m;
scanf("%d%d", &box, &m);
for(int j = box; j <= total; ++j)
dp[i][j] = dp[i - ][j - box]; //假设先买第i个盒子
for(int j = ; j < m; ++j)
{//对盒子里的物品进行01背包
int c, w;
scanf("%d%d", &c, &w);
for(int k = total; k >= c; --k)
if(dp[i][k - c] != -)
dp[i][k] = max(dp[i][k], dp[i][k - c] + w);
}
for(int j = ; j <= total; ++j)
dp[i][j] = max(dp[i][j], dp[i - ][j]); //决策是否买第i个盒子
}
printf("%d\n", dp[n][total]);
}
return ;
}
代码君
另外，可以用滚动数组来优化空间