Facebook
From Beige Tern, 2 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 44
  1. void KnapsackDynamic(Item* items, int itemCount, int knapsackSize)
  2. {
  3.         int** knapsackValues = CreateArray<int>(itemCount + 1, knapsackSize + 1);
  4.         SetDefaultValues(knapsackValues, 0, itemCount + 1, knapsackSize + 1);
  5.  
  6.         int** knapsackWeights = CreateArray<int>(itemCount + 1, knapsackSize + 1);
  7.         SetDefaultValues(knapsackWeights, 0, itemCount + 1, knapsackSize + 1);
  8.  
  9.         int** indexes = CreateArray<int>(itemCount + 1, knapsackSize + 1);
  10.         SetDefaultValues(indexes, 0, itemCount + 1, knapsackSize + 1);
  11.  
  12.         int newValue{};
  13.         int repeatedValue{};
  14.         int knownValue{};
  15.         int newWeight{};
  16.         bool noRepeats = true;
  17.  
  18.         for (int i = 1; i <= itemCount; i++) {
  19.                 noRepeats = true;
  20.                 for (int j = 1; j <= knapsackSize; j++) {
  21.                         if (items[i - 1].weight <= j) {
  22.                                 repeatedValue = 0;
  23.                                 //check if adding another repetition of this object won't overflow knapsack
  24.                                 if ((knapsackWeights[i][j - 1] + items[i - 1].weight) <= j)
  25.                                         repeatedValue = items[i - 1].price + knapsackValues[i][j - 1];
  26.  
  27.                                 //newValue = new item + value from previous iteration
  28.                                 //items[i - 1] beacuse indexing starts from 0, so first item is on index 0
  29.                                 newValue = items[i - 1].price + knapsackValues[i - 1][j - items[i - 1].weight];
  30.  
  31.                                 //Determine if repeating new item will give greater value than adding to previous iteration
  32.                                 knownValue = max(knapsackValues[i - 1][j], knapsackValues[i][j-1]);
  33.                                
  34.                                 //std::cout << knownValue << " " << repeatedValue << " " << newValue <<" "<<noRepeats<< "\n";
  35.  
  36.                                 int index = i;
  37.  
  38.                                 //if new value greater than in previous iteration and greater or equal to repetition
  39.                                 //set to knapsack value and weight of new element
  40.                                 if (newValue >= knownValue and newValue >= repeatedValue) {
  41.                                         newWeight = items[i - 1].weight + knapsackWeights[i - 1][j - items[i - 1].weight];
  42.                                         noRepeats = true;
  43.                                 }
  44.  
  45.                                 //else if repeated value is greater than in previous iteration
  46.                                 //set to knapsack value and weight of repeated item
  47.                                 else if (repeatedValue >= knownValue) {
  48.                                         newValue = repeatedValue;
  49.                                         newWeight = items[i - 1].weight + knapsackWeights[i][j - 1];
  50.                                         noRepeats = false;
  51.                                 }
  52.  
  53.                                 else {
  54.                                         //if no repeated item was added, copy values from above row
  55.                                         if (noRepeats) {
  56.                                                 newValue = knownValue;
  57.                                                 if (i > 2) {
  58.                                                         newWeight = knapsackWeights[i - 1][j];
  59.                                                         index = indexes[i - 1][j];
  60.                                                 }
  61.                                                 else
  62.                                                 {
  63.                                                         newWeight = items[i - 1].weight;
  64.                                                 }
  65.                                         }
  66.                                         //if repeated item was added, copy values from cell in array on left
  67.                                         else if (knapsackValues[i][j - 1] < knapsackValues[i-1][j]) {
  68.                                                 newValue = knapsackValues[i-1][j];
  69.                                                 newWeight = knapsackWeights[i-1][j];
  70.                                                 index = indexes[i-1][j];
  71.                                         }
  72.                                         //if repeated item was added, copy values from cell in array on left
  73.                                         else {
  74.                                         newValue = knapsackValues[i][j - 1];
  75.                                         newWeight = knapsackWeights[i][j - 1];
  76.                                         index = indexes[i][j - 1];
  77.                                 }
  78.                                 }
  79.  
  80.                                 knapsackValues[i][j] = newValue;
  81.                                 knapsackWeights[i][j] = newWeight;
  82.                                 indexes[i][j] = index;
  83.  
  84.                                 //ShowArray(knapsackValues[i], knapsackSize + 1, 3);
  85.                                 //ShowArray(knapsackWeights[i], knapsackSize + 1, 3);
  86.                                
  87.                         }
  88.                         //if item too large copy values from above
  89.                         else {
  90.                                 knapsackValues[i][j] = knapsackValues[i - 1][j];
  91.                                 knapsackWeights[i][j] = knapsackWeights[i - 1][j];
  92.                                 indexes[i][j] = indexes[i - 1][j];
  93.                         }
  94.                 }
  95.  
  96.                 //std::cout << "\n";
  97.         }
  98.         std::cout << "Values: \n";
  99.         ShowArray(knapsackValues, itemCount + 1, knapsackSize + 1, 3);
  100.  
  101.         std::cout << "Weights: \n";
  102.         ShowArray(knapsackWeights, itemCount + 1, knapsackSize + 1, 3);
  103.  
  104.         std::cout << "Indexes: \n";
  105.         ShowArray(indexes, itemCount + 1, knapsackSize + 1, 3);
  106.  
  107.         int sizeLeft = knapsackSize;
  108.         int index = indexes[itemCount][sizeLeft];
  109.         std::cout << "Items: \n";
  110.         while (sizeLeft > 0 and indexes[itemCount][sizeLeft] != 0) {
  111.                 //std::cout<< index<<" "<< items[index-1].weight<<" "<< sizeLeft;
  112.                 index = indexes[itemCount][sizeLeft];
  113.                 std::cout <<"\t- " <<items[index-1].name<<"\n";
  114.                 sizeLeft -= items[index-1].weight;
  115.         }
  116.         std::cout << "\n";
  117.  
  118. }