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. return dp[0][max_wt];
  33. }
  34. }
  35. int main()
  36. {
  37. cin>>n;
  38. for(int i=0;i<n;i++)
  39. {
  40. cin>>wt[i];
  41. }
  42. for(int i=0;i<n;i++)
  43. {
  44. cin>>val[i];
  45. }
  46. cin>>max_wt;
  47. for(int i=0;i<n;i++)
  48. {
  49. for(int j=0;j<=max_wt;j++)
  50. {
  51. dp[i][j]=-1;
  52. }
  53. }
  54. int max_val=knapsack_Iter(0,max_wt);
  55. cout<<max_val<<endl;
  56. }
  57.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
7
5 7 3 8 4 6 9
12 15 8 9 11 13 20
15
stdout
copy 
-1
https://ideone.com/woEhWw
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!