给你一些物品，每个物品有自己的价值和花费，每个物品都对应一个箱子，每个箱子有价钱，买这个物品必须买相应的箱子，给你一个价钱，问最多可以获得多少价值
<提示：多个物品可能同时对应着一个箱子>。
思路：
典型的有依赖的背包，每个箱子是“主件” 每个箱子所对应的物品是他的“附件”，有依赖的背包的过程就是把没一组主件和附件的集合中附件跑一遍01背包，然后把主件强加到跑完后的数组里，然后再在虽有的集合中选择最优的dp[i]的值，这样更新到最后就行了，这样更新 跑附件之间的01背包后强加主件是对应着题意的必须有盒子，而集合和集合之间的更新是对应着 可以再多可集合中选择最优。
#include<stdio.h> #include<string.h> #define N 1100000 int dp[N],tmp[N]; int maxx(int x,int y) { return x > y ? x : y; } int main () { int n,m,i,j,k,c,w,p,nn; while(~scanf("%d %d",&n,&m)) { memset(dp,0,sizeof(dp)); memset(tmp,sizeof(tmp)); for(i = 1 ;i <= n ;i ++) { memcpy(tmp,dp,sizeof(dp)); scanf("%d %d",&p,&nn); for(j = 1 ;j <= nn ;j ++) { scanf("%d %d",&w,&c); for(k = m ;k >= w ;k --) tmp[k] = maxx(tmp[k],tmp[k-w] + c); } for(j = p ;j <= m ;j ++) dp[j] = maxx(dp[j],tmp[j-p]); } printf("%d\n",dp[m]); } return 0; }
