SHARE
TWEET

Untitled

AdrianMadajewski May 28th, 2020 929 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void knapsackBrute(std::vector<Item> items, int knapsackCapacity) {
  2.     int numberOfItems = items.size();
  3.     int fmax = 0;
  4.     int wmax = 0;
  5.     int solution = 0;
  6.  
  7.     int maxLoop = static_cast<int>(std::pow(2, numberOfItems));
  8.     for (int X = 1; X < maxLoop; ++X) {
  9.    
  10.         int weightX = 0;
  11.         int valueX = 0;
  12.         int index = numberOfItems - 1;
  13.  
  14.         // For each bit of X value
  15.         while (X) {
  16.             if (X & 1) {
  17.                 weightX += items[index].weight;
  18.                 valueX += items[index].value;
  19.             }
  20.             X >>= 1;
  21.             index -= 1;
  22.         }
  23.  
  24.         if (weightX <= knapsackCapacity) {
  25.             if (valueX >= fmax) {
  26.                 fmax = valueX;
  27.                 wmax = weightX;
  28.                 solution = X;
  29.             }
  30.         }
  31.     }
  32.  
  33.     std::cout << "fmax: " << fmax << '\n';
  34.     std::cout << "wmax: " << wmax << '\n';
  35.     std::cout << "X:    " << solution << '\n';
  36. }
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