fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int knapSack(int W, int wt[], int val[], int n)
  4. {
  5.     int dp[W + 1];
  6.     memset(dp, 0, sizeof(dp));
  7.     for (int i = 1; i < n + 1; i++) {
  8.         for (int w = W; w >= 0; w--) {
  9.             if (wt[i - 1] <= w) dp[w] = max(dp[w],dp[w - wt[i - 1]] + val[i - 1]);
  10.         }
  11.     }
  12.     return dp[W];
  13. }
  14. int main()
  15. {
  16.     int n,wt;
  17.     cin>>n>>wt;
  18.     int weight[n],profit[n];
  19.     for(int a=0;a<n;a++){
  20.         cin>>weight[a];
  21.     }
  22.     for(int a=0;a<n;a++){
  23.         cin>>profit[a];
  24.     }
  25.     int a = sizeof(profit) / sizeof(profit[0]);
  26.     cout << knapSack(wt, weight, profit, a);
  27.     return 0;
  28. }
  29.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3 4
1 1 1
2 2 2
stdout
copy 
6
https://ideone.com/kKfCEL
language:
C++14 (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!