Unbounded Knapsack

核心概念

跟 0/1 Knapsack 唯一不一樣的地方就只有 unbounded knapsack 每個 item 可以用無限次。

簡介

暴力解的程式碼如下：

using namespace std;

#include <iostream>
#include <vector>

class Knapsack {

public:
  int solveKnapsack(const vector<int> &profits, const vector<int> &weights, int capacity) {
    return this->knapsackRecursive(profits, weights, capacity, 0);
  }

private:
  int knapsackRecursive(const vector<int> &profits, const vector<int> &weights, int capacity,
                        int currentIndex) {
    // base checks
    if (capacity <= 0 || profits.empty() || weights.size() != profits.size() ||
        currentIndex >= profits.size()) {
      return 0;
    }

    // recursive call after choosing the items at the currentIndex, note that we recursive call on
    // all items as we did not increment currentIndex
    int profit1 = 0;
    if (weights[currentIndex] <= capacity) {
      profit1 = profits[currentIndex] +
                knapsackRecursive(profits, weights, capacity - weights[currentIndex], currentIndex);
    }

    // recursive call after excluding the element at the currentIndex
    int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);

    return max(profit1, profit2);
  }
};

int main(int argc, char *argv[]) {
  Knapsack *ks = new Knapsack();
  vector<int> profits = {15, 50, 60, 90};
  vector<int> weights = {1, 3, 4, 5};
  cout << ks->solveKnapsack(profits, weights, 8) << endl;
  cout << ks->solveKnapsack(profits, weights, 6) << endl;

  delete ks;
}

Memoization 的程式碼如下：

using namespace std;

#include <iostream>
#include <vector>

class Knapsack {

public:
  int solveKnapsack(const vector<int> &profits, const vector<int> &weights, int capacity) {
    vector<vector<int>> dp(profits.size(), vector<int>(capacity + 1));
    return this->knapsackRecursive(dp, profits, weights, capacity, 0);
  }

private:
  int knapsackRecursive(vector<vector<int>> &dp, const vector<int> &profits,
                        const vector<int> &weights, int capacity, int currentIndex) {

    // base checks
    if (capacity <= 0 || profits.empty() || weights.size() != profits.size() ||
        currentIndex >= profits.size()) {
      return 0;
    }

    // check if we have not already processed a similar sub-problem
    if (!dp[currentIndex][capacity]) {
      // recursive call after choosing the items at the currentIndex, note that we
      // recursive call on all items as we did not increment currentIndex
      int profit1 = 0;
      if (weights[currentIndex] <= capacity) {
        profit1 =
            profits[currentIndex] +
            knapsackRecursive(dp, profits, weights, capacity - weights[currentIndex], currentIndex);
      }

      // recursive call after excluding the element at the currentIndex
      int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);

      dp[currentIndex][capacity] = max(profit1, profit2);
    }

    return dp[currentIndex][capacity];
  }
};

int main(int argc, char *argv[]) {
  Knapsack *ks = new Knapsack();
  vector<int> profits = {15, 50, 60, 90};
  vector<int> weights = {1, 3, 4, 5};
  cout << ks->solveKnapsack(profits, weights, 8) << endl;
  cout << ks->solveKnapsack(profits, weights, 6) << endl;

  delete ks;
}

DP 解法的程式碼如下：

using namespace std;

#include <iostream>
#include <vector>

class Knapsack {

public:
  int solveKnapsack(const vector<int> &profits, const vector<int> &weights, int capacity) {
    // base checks
    if (capacity <= 0 || profits.empty() || weights.size() != profits.size()) {
      return 0;
    }

    int n = profits.size();
    vector<vector<int>> dp(n, vector<int>(capacity + 1));

    // populate the capacity=0 columns
    for (int i = 0; i < n; i++) {
      dp[i][0] = 0;
    }

    // process all sub-arrays for all capacities
    for (int i = 0; i < n; i++) {
      for (int c = 1; c <= capacity; c++) {
        int profit1 = 0, profit2 = 0;
        if (weights[i] <= c) {
          profit1 = profits[i] + dp[i][c - weights[i]];
        }
        if (i > 0) {
          profit2 = dp[i - 1][c];
        }
        dp[i][c] = profit1 > profit2 ? profit1 : profit2;
      }
    }

    // maximum profit will be in the bottom-right corner.
    return dp[n - 1][capacity];
  }
};

int main(int argc, char *argv[]) {
  Knapsack *ks = new Knapsack();
  vector<int> profits = {15, 50, 60, 90};
  vector<int> weights = {1, 3, 4, 5};
  cout << ks->solveKnapsack(profits, weights, 8) << endl;
  cout << ks->solveKnapsack(profits, weights, 6) << endl;

  delete ks;
}