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