hdu 3449 consumer 有依赖的背包问题

前端之家收集整理的这篇文章主要介绍了hdu 3449 consumer 有依赖的背包问题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目链接

题意:

给你一些物品,每个物品有自己的价值和花费,每个物品都对应一个箱子,每个箱子有价钱,买这个物品必须买相应的箱子,给你一个价钱,问最多可以获得多少价值

<提示:多个物品可能同时对应着一个箱子>。


思路;

这道题是一个基础的有依赖的背包问题,也很明显,要想买某个物品,则其对应的箱子必须要买才可以.那么每个箱子是一个主件,每个箱子对应的这些物品为附件.根据背包九讲当中所讲述的,先对每个主件的附件跑一遍01背包,然后再把主件强加到数组里,然后dp最优解.

  1. #include<iostream>
  2. #include<string.h>
  3. #include<stdio.h>
  4. #include<algorithm>
  5. #define Ri(a) scanf("%d",&a)
  6. #define Rl(a) scanf("%lld",&a)
  7. #define Rf(a) scanf("%lf",&a)
  8. #define Rs(a) scanf("%s",a)
  9. #define Pi(a) printf("%d\n",(a))
  10. #define Pf(a) printf("%lf\n",(a))
  11. #define Pl(a) printf("%lld\n",(a))
  12. #define Ps(a) printf("%s\n",(a))
  13. #define W(a) while(a--)
  14. #define CLR(a,b) memset(a,(b),sizeof(a))
  15. #define MOD 100000007
  16. #define inf 0x3f3f3f3f
  17. #define exp 0.00000001
  18. #define pii pair<int,int>
  19. #define mp make_pair
  20. #define pb push_back
  21. using namespace std;
  22. typedef long long ll;
  23. const int maxn=1e5+10;
  24. int n,m;
  25. int dp[maxn],f[maxn];
  26. int main()
  27. {
  28. int p,cc,v,w;
  29. while(~Ri(n))
  30. {
  31. Ri(m);
  32. CLR(dp,0);
  33. CLR(f,0);
  34. for(int i=1;i<=n;i++)
  35. {
  36. memcpy(f,dp,sizeof(f));
  37. Ri(p),Ri(cc);
  38. for(int j=1;j<=cc;j++)
  39. {
  40. Ri(v),Ri(w);
  41. for(int k=m-p;k>=v;k--)
  42. f[k]=max(f[k],f[k-v]+w);
  43. }
  44. for(int k=m;k>=p;k--)
  45. dp[k]=max(dp[k],f[k-p]);
  46. }
  47. Pi(dp[m]);
  48. }
  49. return 0;
  50. }

猜你在找的设计模式相关文章