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