daily pastebin goal
42%
SHARE
TWEET

Knapsack Problem C++

keverman Oct 26th, 2018 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct item
  2. {
  3.     int val, wh;
  4. };
  5.  
  6. int knapsack(int W, std::vector<item> V)
  7. {
  8.     std::vector<std::vector<int> > DP(2, std::vector<int>(W + 1, 0));
  9.  
  10.     for (int i = 1; i <= V.size(); i++)
  11.     {
  12.         for (int w = 1; w <= W; w++)
  13.             if(V[i - 1].wh <= w)
  14.                 DP[1][w] = (V[i - 1].wh <= w ? std::max(V[i - 1].val + DP[0][w - V[i - 1].wh], DP[0][w])
  15.                                              : DP[0][w]);
  16.  
  17.         std::swap(DP[0], DP[1]);
  18.     }
  19.  
  20.     return DP[0][W];
  21. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top