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_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.  
  17. for(int i=n-1;i>=0;i--)
  18. {
  19. for(int j=1;j<=max_wt;j++)
  20. {
  21. if(j>=wt[i])
  22. {
  23. int niye=val[i]+dp[i+1][j-wt[i]];
  24. int naniye=dp[i+1][j];
  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. int main()
  36. {
  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. for(int i=0;i<=n;i++)
  49. {
  50. for(int j=0;j<=max_wt;j++)
  51. {
  52. dp[i][j]=-1;
  53. }
  54. }
  55.  
  56. int max=knapsack_Iter(0,max_wt);
  57. cout<<max<<endl;
  58. }
Success #stdin #stdout 0.01s 5308KB
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/xtxwk4
language:
C++ (gcc 8.3)
created:
1 day 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!