题意:
给你一些物品,每个物品有自己的价值和花费,每个物品都对应一个箱子,每个箱子有价钱,买这个物品必须买相应的箱子,给你一个价钱,问最多可以获得多少价值<提示:多个物品可能同时对应着一个箱子>。
思路;
这道题是一个基础的有依赖的背包问题,也很明显,要想买某个物品,则其对应的箱子必须要买才可以.那么每个箱子是一个主件,每个箱子对应的这些物品为附件.根据背包九讲当中所讲述的,先对每个主件的附件跑一遍01背包,然后再把主件强加到数组里,然后dp最优解.
- #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;
- }