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_Iter(int i,int ava_wt)
  7. {
  8. for(int i=0;i<=n;i++)
  9. {
  10. dp[i][0]=0;
  11. }
  12. for(int j=0;j<=max_wt;j++)
  13. {
  14. dp[n][j]=0;
  15. }
  16. for(int i=n-1;i>=0;i--)
  17. {
  18. for(int j=1;j<=max_wt;j++)
  19. {
  20. if(j>=wt[i])
  21. {
  22. int niye=val[i]+dp[i+1][j];
  23. int naniye=dp[i+1][j];
  24.  
  25. dp[i][j]=max(niye,naniye);
  26. }
  27. else
  28. {
  29. dp[i][j]=dp[i+1][j];
  30. }
  31. }
  32. }
  33. return dp[0][max_wt];
  34. }
  35.  
  36. int main()
  37. {
  38. cin>>n;
  39. for(int i=0;i<n;i++)
  40. {
  41. cin>>wt[i];
  42. }
  43. for(int i=0;i<n;i++)
  44. {
  45. cin>>val[i];
  46. }
  47. cin>>max_wt;
  48.  
  49. int max_val=knapsack_Iter(0,max_wt);
  50. cout<<max_val<<endl;
  51. }
  52.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
7
5 7 3 8 4 6 9
12 15 8 9 11 13 20
15
stdout
copy 
88
https://ideone.com/NcEJUO
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!