题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3449
题意：有n个箱子，每个箱子有一个价格v，每个箱子中有若干个物品，规定在购买物品前必须购买包含该物品的箱子，问能买到的最大价值
题解;
有依赖的背包问题
F[i][j]表示前i个箱子花费j元得到的最大价值（不是第i个）
具体思路是在每一个箱子中做一次0/1背包，更新dp数组，再把每个箱子当成一个物品组，做一次分组背包。
具体处理时要注意很多细节问题
下附一个有详细注释的代码，和一些我的个人感悟
#include<stdio.h>
#include<string.h>
#define wsize 100010
#define nsize 65
#define msize 11
int dp[nsize][wsize];
int n,t,box,num;
int max(int a,int b)
{return a>b?a:b;
}
int main ()
{int i,j,k;while(scanf("%d %d",&n,&t)!=EOF){memset(dp,-1,sizeof(dp)); //有依赖关系，要赋初值-1，后判断要用memset(dp[0],0,sizeof(dp[0]));for(i=1;i<=n;i++){scanf("%d %d",&box,&num);for(k=box;k<=t;k++)dp[i][k]=dp[i-1][k-box]; //先让i层买盒子，因为盒子没有价值，所以直接等于上一层的花费+盒子钱，可以脑补一个+0for(j=0;j<num;j++) //在已花费盒子钱的基础上，此时再对dp[i]层做0/1背包，即i层一个盒子多种物品的最大价值 {int c,w;scanf("%d %d",&c,&w); for(k=t;k>=c;k--) {if(dp[i][k-c]!=-1) //注意依赖背包有不可能的情况，这里即k买不到盒子和这个物品，不能装物品//个人理解:如果dp的值等于-1，说明前面不能更新到这个状态，也就是说可能买不到这样的箱子，所以说这个状态是无效的，不能更新dp[i][k]=max(dp[i][k],dp[i][k-c]+w); // 这里不能dp[i][k]=max(dp[i][j],dp[i][k-box-c]+w) 因为已经买过盒子了，这个表达式代表一个盒子基础上一个物品带一个盒子}}for(j=0;j<=t;j++){ //考虑不买这组还是买这组dp[i][j]=max(dp[i-1][j],dp[i][j]); //不要忘了考虑不选当前组的情况（不是必选）}}printf("%d\n",dp[n][t]);}return 0;
}附上我的代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int f[65][100010];
int main()
{int box,num,v,w;while(scanf("%d%d",&n,&m)!=EOF){memset(f,-1,sizeof(f));memset(f[0],0,sizeof(f[0]));for(int i=1;i<=n;i++){scanf("%d%d",&box,&num);for(int j=box;j<=m;j++) f[i][j]=f[i-1][j-box];for(int j=1;j<=num;j++){scanf("%d%d",&w,&v);for(int k=m;k>=w;k--){if(f[i][k-w]!=-1)f[i][k]=max(f[i][k-w]+v,f[i][k]);}}for(int j=0;j<=m;j++)f[i][j]=max(f[i][j],f[i-1][j]);}printf("%d\n",f[n][m]);}
}