fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. int weight[1002],cost[1002],number_of_items,capacity;
  8. int dp[1002][1002];
  9.  
  10. int knapsack(int i,int w)
  11. {
  12.     if(i>=number_of_items)
  13.         return 0;
  14.     if(dp[i][w]!=-1)
  15.         return dp[i][w];
  16.     int profit1=0,profit2=0;
  17.     if(w+weight[i]<=capacity)
  18.         profit1=cost[i]+knapsack(i+1,w+weight[i]);
  19.     profit2=knapsack(i+1,w);
  20.     dp[i][w]=max(profit1,profit2);
  21.     return dp[i][w];
  22. }
  23. int main()
  24. {
  25.     int testcase,number_of_person,sum;
  26.     cin>>testcase;
  27.     while(testcase--)
  28.     {
  29.         sum=0;
  30.         cin>>number_of_items;
  31.         for(int i=0; i<number_of_items; i++)
  32.         {
  33.             cin>>cost[i]>>weight[i];
  34.         }
  35.         cin>>number_of_person;
  36.         for(int i=0; i<number_of_person; i++)
  37.         {
  38.             cin>>capacity;
  39.             memset(dp,-1,sizeof(dp));
  40.             sum+=knapsack(0,0);
  41.         }
  42.         cout<<sum<<endl;
  43.     }
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0s 7228KB
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/iTuikC
language:
C++ (gcc 8.3)
created:
10 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!