0/1 Bounded Knapsack (several variations, along with solution reconstruction and space optimization)

bounded_knapsack.cpp

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cstdio>
#include <utility>

using namespace std;

/**
 * Version 1: Naive Bruteforce (or backtracking if you prefer)
 */
int max_profit_recursive(vector<int>& weights, vector<int>& profits, int leftover_capacity, int index = 0) {
  if (leftover_capacity <= 0 || index >= weights.size()) return 0;

  int profit_if_take = 0;
  if (weights[index] <= leftover_capacity) {
    profit_if_take = profits[index] + max_profit_recursive(weights, profits, leftover_capacity - weights[index], index + 1);
  }

  int profit_if_not_take = max_profit_recursive(weights, profits, leftover_capacity, index + 1);

  return max(profit_if_take, profit_if_not_take);
}

/**
 * Version 2: Recursion with Memoization
 */ 
int max_profit_recursive_dp(vector<int>& weights, vector<int>& profits, int leftover_capacity, vector<vector<int>>& dp, int index = 0) {
  if (leftover_capacity <= 0 || index >= weights.size()) return 0;

  if (dp[index][leftover_capacity] != -1) return dp[index][leftover_capacity];

  int profit_if_take = 0;
  if (weights[index] <= leftover_capacity) {
    profit_if_take = profits[index] + max_profit_recursive_dp(weights, profits, leftover_capacity - weights[index], dp, index + 1);
  }

  int profit_if_not_take = max_profit_recursive_dp(weights, profits, leftover_capacity, dp, index + 1);

  dp[index][leftover_capacity] = max(profit_if_take, profit_if_not_take);
  return dp[index][leftover_capacity];
}

/**
 * Version 3: Iterative DP
 */
int max_profit_iterative_dp(vector<int>& weights, vector<int>& profits, int capacity, vector<vector<int>>& dp) {
  const int N = profits.size();

  for (int i = 0; i < N; i++) dp[i][0] = 0;
  for (int c = 0; c <= capacity; c++) if (weights[0] <= c) dp[0][c] = profits[0];

  for (int i = 1; i < N; i++) {
    for (int c = 1; c <= capacity; c++) {
      int profit_if_take = weights[i] > c ? 0 : profits[i] + dp[i - 1][c - weights[i]];
      int profit_if_not_take = dp[i-1][c];

      dp[i][c] = max(profit_if_take, profit_if_not_take);
    }
  }

  return dp[N-1][capacity];
}

/**
 * Version 4: Iterative DP - Space optimized to O(|C|) from O(N*C)
 */
int max_profit_iterative_dp_space_optimized(vector<int>& weights, vector<int>& profits, int capacity) {
  const int N = profits.size();
  vector<int> dp(capacity + 1);

  for (int c = 0; c <= capacity; c++) if (weights[0] <= c) dp[c] = profits[0];

  for (int i = 1; i < N; i++) {
    vector<int> new_dp(capacity + 1);

    for (int c = 1; c <= capacity; c++) {
      int profit_if_take = weights[i] > c ? 0 : profits[i] + dp[c - weights[i]];
      int profit_if_not_take = dp[c];

      new_dp[c] = max(profit_if_take, profit_if_not_take);
    }

    dp = new_dp;
  }

  return dp[capacity];
}

/**
 * Version 5: Iterative DP - Space optimized to use only one array (in-place updates)
 */
int max_profit_iterative_dp_space_optimized_2(vector<int>& weights, vector<int>& profits, int capacity) {
  const int N = profits.size();
  vector<int> dp(capacity + 1);

  for (int c = 0; c <= capacity; c++) if (weights[0] <= c) dp[c] = profits[0];

  for (int i = 1; i < N; i++) {
    for (int c = 1; c <= capacity; c++) {
      int profit_if_take = weights[i] > c ? 0 : profits[i] + dp[c - weights[i]];
      int profit_if_not_take = dp[c];

      dp[c] = max(profit_if_take, profit_if_not_take);
    }
  }

  return dp[capacity];
}

/**
 * Given the final state of the DP matrix, assembles the actual solution that leads to the max profit.
 */
vector<int> reconstruct(vector<int>& weights, vector<int>& profits, int capacity, vector<vector<int>>& dp) {
  vector<int> solution;

  const int N = weights.size();

  int curr_capacity = capacity;
  int curr_profit = dp[N-1][curr_capacity];

  // note the > 0 and not >= 0. The 0th row is a base case, and doesn't have a 'top' row to check against,
  // so it is handled separately.
  for (int item = N-1; item > 0; item--) {
    int profit_if_not_taken = dp[item - 1][curr_capacity];

    // we came from the top neighbor i.e. we didn't take
    if (profit_if_not_taken == curr_profit) {
      continue;
    }

    // we took the item
    solution.push_back(item);
    int profit_before_taking = curr_profit - profits[item];
    curr_profit = profit_before_taking;

    int capacity_before_taking = curr_capacity - weights[item];
    curr_capacity = capacity_before_taking;
  }

  // if we are left with some non-zero profit, then we must have taken the 0th item as well.
  if (curr_profit != 0) solution.push_back(0);

  reverse(solution.begin(), solution.end());
  return solution;
}

int main() {
  vector<int> profits = {1, 6, 10, 16};
  vector<int> weights = {1, 2, 3, 5};
  int capacity = 7;
  cout << "Recursive: " << max_profit_recursive(weights, profits, capacity) << '\n';

  vector<vector<int>> dp(profits.size(), vector<int>(capacity + 1, -1));
  cout << "Recursive DP: " << max_profit_recursive_dp(weights, profits, capacity, dp) << '\n';

  vector<vector<int>> dp_iter(weights.size(), vector<int>(capacity + 1));
  cout << "Iterative DP: " << max_profit_iterative_dp(weights, profits, capacity, dp_iter) << '\n';

  cout << "Iterative DP (Space optimized): " << max_profit_iterative_dp_space_optimized(weights, profits, capacity) << '\n';
  cout << "Iterative DP (Space optimized v2): " << max_profit_iterative_dp_space_optimized_2(weights, profits, capacity) << '\n';

  cout << "Solution Reconstruction: ";
  vector<int> sol = reconstruct(weights, profits, capacity, dp_iter);
  for (auto s: sol) cout << profits[s] << ",";
  cout << '\n';
}