@H_502_0@题意： 给你一些物品，每个物品有自己的价值和花费，每个物品都对应一个箱子，每个箱子有价钱，买这个物品必须买相应的箱子，给你一个价钱，问最多可以获得多少价值
@H_502_0@<提示：多个物品可能同时对应着一个箱子>。 @H_502_0@
@H_502_0@思路； @H_502_0@这道题是一个基础的有依赖的背包问题,也很明显,要想买某个物品,则其对应的箱子必须要买才可以.那么每个箱子是一个主件,每个箱子对应的这些物品为附件.根据背包九讲当中所讲述的,先对每个主件的附件跑一遍01背包,然后再把主件强加到数组里,然后dp最优解. @H_502_0@
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #define Ri(a) scanf("%d",&a) #define Rl(a) scanf("%lld",&a) #define Rf(a) scanf("%lf",&a) #define Rs(a) scanf("%s",a) #define Pi(a) printf("%d\n",(a)) #define Pf(a) printf("%lf\n",(a)) #define Pl(a) printf("%lld\n",(a)) #define Ps(a) printf("%s\n",(a)) #define W(a) while(a--) #define CLR(a,b) memset(a,(b),sizeof(a)) #define MOD 100000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int,int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; int n,m; int dp[maxn],f[maxn]; int main() { int p,cc,v,w; while(~Ri(n)) { Ri(m); CLR(dp,0); CLR(f,0); for(int i=1;i<=n;i++) { memcpy(f,dp,sizeof(f)); Ri(p),Ri(cc); for(int j=1;j<=cc;j++) { Ri(v),Ri(w); for(int k=m-p;k>=v;k--) f[k]=max(f[k],f[k-v]+w); } for(int k=m;k>=p;k--) dp[k]=max(dp[k],f[k-p]); } Pi(dp[m]); } return 0; }
