fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,max_wt;
  4. int wt[100],val[100];
  5. int dp[100][1000];
  6. int knapsack(int i,int ava_wt)
  7. {
  8. if(ava_wt==0)
  9. return 0;
  10. if(i==n)
  11. return 0;
  12. if(dp[i][ava_wt]!=-1)
  13. return dp[i][ava_wt];
  14. if(ava_wt>=wt[i])
  15. {
  16. int niye=val[i]+knapsack(i+1,ava_wt-wt[i]);
  17. int naniye=knapsack(i+1,ava_wt);
  18. return max(niye,naniye);
  19. }
  20. else
  21. {
  22. return knapsack(i+1,ava_wt);
  23. }
  24. }
  25.  
  26.  
  27. int main()
  28. {
  29. cin>>n;
  30. for(int i=0;i<n;i++)
  31. {
  32. cin>>wt[i];
  33. }
  34. for(int i=0;i<n;i++)
  35. {
  36. cin>>val[i];
  37. }
  38. cin>>max_wt;
  39.  
  40. int max_val=knapsack(0,max_wt);
  41. cout<<max_val<<endl;
  42. }
  43.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
7
2 3 5 6 9 12 15
9
stdout
copy 
0
https://ideone.com/eV02AD
language:
C++ (gcc 8.3)
created:
7 days 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!