fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,max_wt;
  4. int val[100],wt[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 dp[i][ava_wt]=max(niye,naniye);
  19. }
  20. else
  21. {
  22. return knapsack(i+1,ava_wt);
  23. }
  24. }
  25.  
  26. int main()
  27. {
  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. for(int i=0;i<=n;i++)
  40. {
  41. for(int j=0;j<=max_wt;j++)
  42. {
  43. dp[i][j]=-1;
  44. }
  45. }
  46.  
  47. int max=knapsack(0,max_wt);
  48. cout<<max<<endl;
  49. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
7
5 7 3 8 4 6 9 
12 15 8 9 11 13 20
15
stdout
copy 
36
https://ideone.com/dJHpqb
language:
C++ (gcc 8.3)
created:
16 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!