SHARE
TWEET

Untitled

AdrianMadajewski Jun 1st, 2020 687 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void knapsackDynamic(std::vector<Item> items, const int knapsackCapacity) {
  2.     const int numberOfItems = items.size();
  3.    
  4.     // DP matrix initialization
  5.     int** DPmatrix = new int* [numberOfItems + 1]{};
  6.     for (int itemIndex = 0; itemIndex <= numberOfItems; ++itemIndex) {
  7.         DPmatrix[itemIndex] = new int[knapsackCapacity + 1]{};
  8.     }
  9.  
  10.     printMatrix(DPmatrix, numberOfItems + 1, knapsackCapacity + 1);
  11.    
  12.     for (int itemIndex = 1; itemIndex <= numberOfItems; ++itemIndex) {
  13.         int value = items[itemIndex - 1].value;
  14.         int weight = items[itemIndex - 1].weight;
  15.  
  16.         for (int slot = 0; slot <= knapsackCapacity; ++slot) {
  17.            
  18.             if (weight > slot) {
  19.                 DPmatrix[slot][itemIndex] = DPmatrix[itemIndex - 1][slot];
  20.             }
  21.             else {
  22.                 int previous = DPmatrix[itemIndex - 1][slot];
  23.                 int possibleNext = DPmatrix[itemIndex - 1][slot - weight] + value;
  24.                 DPmatrix[itemIndex][slot] = std::max(previous, possibleNext);
  25.             }
  26.         }
  27.     }
  28.    
  29.  
  30.     std::cout << '\n';
  31.    
  32.     printMatrix(DPmatrix, numberOfItems + 1, knapsackCapacity + 1);
  33.  
  34.  
  35.     // Release allocated memory
  36.     for (int i = 0; i <= numberOfItems; ++i) {
  37.         delete[] DPmatrix[i];
  38.     }
  39.     delete[] DPmatrix;
  40. }
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