题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3449
题目大意：有很多个箱子和一些物品，想买箱子中的物品必须先买下箱子，求在规定的钱数里最多能买多大价值的东西
emmm，没什么好说的，就是板子套一套完事了。依赖背包分为主件和附件，解决这类问题就是对每个主件从dp数组中copy一个tmp数组，然后让这个主件中的附件对tmp数组做01背包，之后对每个值加上主件的体积和价值求一个max就ok了
以下是AC代码：
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int mac=1e5+10; int dp[mac],f[mac]; int poj[55][20],s[55],bag[55],val[55][20]; int main() { int n,w; while (~scanf ("%d%d",&n,&w)) { memset(dp,0,sizeof dp); for (int i=1; i<=n; i++) { int m; scanf ("%d%d",&bag[i],&m); s[i]=m; for (int j=1; j<=m; j++) scanf ("%d%d",&poj[i][j],&val[i][j]); } for (int i=1; i<=n; i++) { memcpy(f,dp,sizeof dp); for (int j=1; j<=s[i]; j++) for (int k=w; k>=poj[i][j]; k--) f[k]=max(f[k],f[k-poj[i][j]]+val[i][j]); for (int j=w; j>=bag[i]; j--) dp[j]=max(dp[j],f[j-bag[i]]+0); } printf("%d\n",dp[w]); } return 0; }
原文：https://www.cnblogs.com/lonely-wind-/p/13263529.html