fork download
copy 
  1.  #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. using namespace std;
  5. #define max 1000
  6. int cost[max];
  7. int  weight[max];
  8. int  dp[max][31];
  9. int  CAP,sum,m;
  10. int func(int i,int w);
  11. int main()
  12. {
  13. 	int  i,j,n,t,p;
  14. 	scanf("%d",&t);
  15. 	for(i=1;i<=t;i++)
  16. 	{
  17. 		scanf("%d",&m);
  18. 		for(j=0;j<m;j++)
  19. 		{
  20. 			scanf("%d%d",&cost[j],&weight[j]);
  21. 		}
  22. 		scanf("%d",&p);
  23. 		sum=0;
  24. 		for(j=1;j<=p;j++)
  25. 		{
  26. 			memset(dp,-1,sizeof(dp));
  27. 			scanf("%d",&CAP);
  28. 			sum=sum+func(0,0);
  29. 		}
  30. 		printf("%d\n",sum);
  31. 	}
  32. 	return 0;
  33. }
  34. int func(int i,int w)
  35. {
  36. 	if(i==m)
  37. 		return 0;
  38. 	if(dp[i][w]=!-1)
  39. 		return dp[i][w];
  40. 	int  profit1=0,profit2=0;
  41. 	if(w+weight[i]<=CAP)
  42. 		profit1=cost[i]+func(i+1,w+weight[i]);
  43. 	 profit2=func(i+1,w);
  44. 	 if(profit1>profit2)
  45. 		 dp[i][w]=profit1;
  46. 	 else
  47. 		 dp[i][w]=profit2;
  48. 	 return dp[i][w];
  49. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
2

3

72 17

44 23

31 24

1

26

6

64 26

85 22

52 4

99 18

39 13

54 9

4

23

20

20

26
stdout
copy 
72
514
https://ideone.com/egHyyE
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!