fork download
  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. int weights[1005],num_person;
  5. int prices[1005],person_max;int takeItem, skipItem;;
  6. int waight,price,num,sum=0,arr[1005][35];
  7. int solve(int index, int weight)
  8. {
  9.  
  10. if(arr[index][weight]!=-1)
  11. return arr[index][weight];
  12. if(index==num)
  13. {
  14. if(weight <= person_max)
  15. {
  16. return arr[index][weight]=price;
  17.  
  18. }
  19. else
  20. return arr[index][weight]= 0;
  21. }
  22. int takeItem, skipItem;
  23. if(weight+weights[index]<=person_max)
  24. {
  25. takeItem = solve(index + 1, weight + weights[index])+ price + prices[index];
  26. }
  27. skipItem = solve(index + 1, weight);
  28. return arr[index][weight]=max(takeItem, skipItem);
  29. }
  30. int main()
  31. {
  32. int testCases;
  33. cin>>testCases;
  34. for(int i=0;i<testCases;i++)
  35. {
  36. cin>>num;
  37. for(int j=0;j<num;j++)
  38. {
  39. cin>>prices[j]>>weights[j];
  40. }
  41. cin>>num_person;
  42. for(int j=0;j<num_person;j++)
  43. {
  44. cin>>person_max;
  45. for(int k=0;k<1005;k++)
  46. for(int l=0;l<35;l++)
  47. arr[k][l]=-1;
  48. sum+= solve(0, 0);
  49. }
  50. cout<<sum << endl;
  51. sum=0;
  52. }
  53. return 0;
  54. }
Success #stdin #stdout 0.02s 2828KB
stdin
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
116
1079