题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3449
题目大意：
fj打算去买一些东西，在那之前，他需要一些盒子去装他打算要买的不同的物品。每一个盒子有特定要装的东西（就是说如果他要买这些东西里的一个，他不得不先买一个盒子）。每一种物品都有自己的价值，现在FJ只有W元去购物，他打算用这些钱买价值最高的东西。
思路：
这是有依赖的背包，每件物品买之前必须买特定的盒子
所以先对每一个箱子进行01背包，保存可以凑出的所有的花费和该花费的最大价值，这是一组中的所有状态，且只能取一个或者不取，背包转化成分组背包，然后就可以做了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> Pair ;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + ;
int T, n, m, cases;
struct node
{
int price;
int num;
int price_sum;
int cost[], value[];
int dp[];
};
node a[];
int dp[maxn];
int main()
{
while(cin >> n >> m)
{
memset(dp, , sizeof(dp));
memset(a, , sizeof(a));
for(int i = ; i < n; i++)
{
scanf("%d%d", &a[i].price, &a[i].num);
a[i].price_sum = ;
for(int j = ; j < a[i].num; j++)
{
scanf("%d%d", &a[i].cost[j], &a[i].value[j]);
a[i].price_sum += a[i].cost[j];
}
}
for(int i = ; i < n; i++)//对，每个箱子预处理出所有可凑出的花费和该花费的最大价值
{
memset(a[i].dp, -, sizeof(a[i].dp));
a[i].dp[] = ;
for(int j = ; j < a[i].num; j++)
{
for(int k = a[i].price_sum; k >= a[i].cost[j]; k--)
if(a[i].dp[k - a[i].cost[j]] >= )a[i].dp[k] = max(a[i].dp[k], a[i].dp[k - a[i].cost[j]] + a[i].value[j]);
}/*
for(int j = 0; j <= a[i].price_sum; j++)
cout<<a[i].dp[j]<<" ";
cout<<endl;*/
}
for(int i = ; i < n; i++)//枚举每一个的箱子
{
vector<Pair>d;
for(int j = ; j <= a[i].price_sum; j++)//将该箱子的所有状态存下来
{
if(a[i].dp[j] > )
d.push_back(Pair(j + a[i].price, a[i].dp[j]));
}
for(int v = m; v >= ; v--)//枚举花费
{
for(int j = ; j < d.size(); j++)//枚举改组的状态
if(v >= d[j].first)
dp[v] = max(dp[v], dp[v - d[j].first] + d[j].second);
}
}
cout<<dp[m]<<endl;
}
return ;
}
还有一种写法，在dp的时候把预处理和状态转化合并起来，时间复杂度降低了一点
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> Pair ;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + ;
int T, n, m, cases;
int a[];
int dp[][];
struct node
{
int v, w;
};
vector<node>G[];
int main()
{
while(cin >> n >> m)
{
memset(dp, , sizeof(dp));
for(int i = ; i <= n; i++)G[i].clear();
int tot, x, y;
for(int i = ; i <= n; i++)
{
scanf("%d%d", &a[i], &tot);
for(int j = ; j < tot; j++)
{
scanf("%d%d", &x, &y);
G[i].push_back(node{x, y});
}
} for(int i = ; i <= n; i++)//枚举每种箱子
{
for(int j = ; j < a[i]; j++)dp[i][j] = -;
for(int j = a[i]; j <= m; j++)dp[i][j] = dp[i - ][j - a[i]];//这里是确保先购买购物车 for(int j = ; j < G[i].size(); j++)//在购物车内进行01背包
{
for(int k = m; k >= G[i][j].v; k--)
{
if(dp[i][k - G[i][j].v] != -)
dp[i][k] = max(dp[i][k], dp[i][k - G[i][j].v] + G[i][j].w);
}
}
for(int j = ; j <= m; j++)dp[i][j] = max(dp[i - ][j], dp[i][j]);//和之前的值比较
}
cout<<dp[n][m]<<endl;
}
return ;
}