Solving the 0 1 Knapsack Problem: From Recursion to Dynamic Programming

Given a list of items, each with a weight and a value, determine the maximum value you can achieve without exceeding a given weight capacity (maxWeight). You can only include each item once, and you must decide whether to include or exclude each item.

Example
Let's take an example where you have the following items:

• Weights: [1, 2, 4, 5]
• Values: [5, 4, 8, 6]
• Maximum Weight Capacity: 5

The goal is to maximize the total value of items in the knapsack without exceeding the weight capacity of 5.

Approach 1: Recursive (Brute Force) Solution
The first approach uses recursion to explore all possible combinations of including or excluding each item. The basic idea is to try both options for every item and take the maximum value from these choices.

int knapsackRecursive(vector<int> &weights, vector<int> &values, int n, int maxWeight, int currentIndex) {
  if (currentIndex >= n) {
    return 0;
  }

  int include = 0;
  if (maxWeight - weights[currentIndex] >= 0) {
    include = values[currentIndex] + knapsackRecursive(weights, values, n, maxWeight - weights[currentIndex], currentIndex + 1);
  }

  int exclude = knapsackRecursive(weights, values, n, maxWeight, currentIndex + 1);

  return max(include, exclude);
}

Time Complexity:

• O(2^n) because each item can either be included or excluded, leading to an exponential number of combinations.

Space Complexity:

• O(n) due to the depth of the recursion stack.

Approach 2: Memoization
To optimize the recursive approach, we can use memoization. This technique stores the results of subproblems, avoiding redundant calculations.

int knapsackMemoization(vector<int> &weights, vector<int> &values, int n, int maxWeight, int currentIndex, vector<vector<int>> &memo) {
  if (currentIndex >= n) {
    return 0;
  }

  if (memo[maxWeight][currentIndex] != -1) {
    return memo[maxWeight][currentIndex];
  }

  int include = 0;
  if (maxWeight - weights[currentIndex] >= 0) {
    include = values[currentIndex] + knapsackMemoization(weights, values, n, maxWeight - weights[currentIndex], currentIndex + 1, memo);
  }

  int exclude = knapsackMemoization(weights, values, n, maxWeight, currentIndex + 1, memo);

  memo[maxWeight][currentIndex] = max(include, exclude);
  return memo[maxWeight][currentIndex];
}

Time Complexity:

• O(n * maxWeight) because each subproblem is solved only once and stored for future reference.

Space Complexity:

• O(n * maxWeight) due to the storage required for the memoization table.

Approach 3: Tabulation (Bottom-Up Dynamic Programming)
The tabulation approach eliminates recursion by iteratively solving subproblems and storing the results in a table. This approach builds the solution from the base cases upward.

int knapsackTabulation(vector<int> &weights, vector<int> &values, int n, int maxWeight) {
  vector<vector<int>> dp(maxWeight + 1, vector<int>(n + 1, -1));

  for (int k = 0; k <= maxWeight; k++) {
    dp[k][n] = 0;
  }

  for (int i = 0; i <= maxWeight; i++) {
    for (int j = n - 1; j >= 0; j--) {
      int include = 0;
      if (i - weights[j] >= 0) {
        include = values[j] + dp[i - weights[j]][j + 1];
      }
      int exclude = dp[i][j + 1];
      dp[i][j] = max(include, exclude);
    }
  }

  return dp[maxWeight][0];
}

Time Complexity:

• O(n * maxWeight) because we fill a table of size n * maxWeight.

Space Complexity:

• O(n * maxWeight) for the table that stores the results of subproblems.

Approach 4: Optimized Tabulation (2D to 1D)
By observing that each row of the table only depends on the previous row, we can reduce space complexity by using two 1D arrays instead of a 2D table.

int knapsackTabulationOptimized2D1D(vector<int> &weights, vector<int> &values, int n, int maxWeight) {
  vector<int> curr(maxWeight + 1, -1);
  vector<int> next(maxWeight + 1, 0);

  for (int j = n - 1; j >= 0; j--) {
    for (int i = 0; i <= maxWeight; i++) {
      int include = 0;
      if (i - weights[j] >= 0) {
        include = values[j] + next[i - weights[j]];
      }
      int exclude = next[i];
      curr[i] = max(include, exclude);
    }
    next = curr;
  }
  return next[maxWeight];
}

Time Complexity:

• O(n * maxWeight) similar to the previous approach.

Space Complexity:

• O(maxWeight) reduced from O(n * maxWeight) to O(maxWeight).

Approach 5: Further Optimized Tabulation (1D Array)
Finally, we can optimize even further by realizing that we only need one 1D array to store the results, updating it in place.

int knapsackTabulationOptimized1D(vector<int> &weights, vector<int> &values, int n, int maxWeight) {
  vector<int> dp(maxWeight + 1, 0);

  for (int j = n - 1; j >= 0; j--) {
    for (int i = maxWeight; i >= 0; i--) {
      int include = 0;
      if (i - weights[j] >= 0) {
        include = values[j] + dp[i - weights[j]];
      }
      int exclude = dp[i];
      dp[i] = max(include, exclude);
    }
  }
  return dp[maxWeight];
}

Time Complexity:

• O(n * maxWeight) as it iterates over all possible subproblems.

Space Complexity:

• O(maxWeight) making this the most space-efficient approach.

Conclusion
The Knapsack problem can be solved using various approaches, ranging from brute-force recursion to highly optimized dynamic programming techniques. The choice of method depends on the constraints and requirements of the problem. As we've seen, by analyzing the problem and leveraging dynamic programming, we can significantly reduce both time and space complexities.