Learnitweb

0/1 Knapsack Coding Pattern

1. Introduction

The 0/1 Knapsack problem is a classic Dynamic Programming (DP) problem used to teach decision-based optimization.

Problem Statement:

Given N items, each with a weight w[i] and a value v[i], and a knapsack with capacity W, select a subset of items to maximize the total value without exceeding the capacity.
Each item can be included or excluded (hence 0/1).

Example:

Weights:  [2, 3, 4, 5]
Values:   [3, 4, 5, 6]
Capacity: 5
Output: 7   (choose items with weight 2 and 3, value 3+4=7)

2. When to Use the 0/1 Knapsack Pattern

Use this pattern when:

  1. You need to maximize/minimize a value under constraints.
  2. Each element/item can be taken at most once.
  3. Problems involve decision-making for each element: include or exclude.
  4. Problems can be framed as subproblems based on item index and remaining capacity.

Problem Indicators:

  • “Maximize value with weight constraint”
  • “Subset selection with limited capacity”
  • “Decision problem: pick or skip elements to optimize”

3. Core Idea

The core idea is dynamic programming with choice:

At each item, you have two options:

  1. Include the item (if it fits): value = v[i] + dp[i-1][W - w[i]]
  2. Exclude the item: value = dp[i-1][W]

Then take the maximum of both choices:

dp[i][W] = max(include, exclude)

4. Recursive (Backtracking) Approach

public int knapsackRecursive(int[] weights, int[] values, int n, int capacity) {
    if (n == 0 || capacity == 0) return 0;

    if (weights[n-1] > capacity) {
        // cannot include item
        return knapsackRecursive(weights, values, n-1, capacity);
    } else {
        int include = values[n-1] + knapsackRecursive(weights, values, n-1, capacity - weights[n-1]);
        int exclude = knapsackRecursive(weights, values, n-1, capacity);
        return Math.max(include, exclude);
    }
}

Drawbacks:

  • Exponential time complexity: O(2^N)
  • Recomputes overlapping subproblems

5. Top-Down Dynamic Programming (Memoization)

public int knapsackTopDown(int[] weights, int[] values, int n, int capacity) {
    int[][] dp = new int[n+1][capacity+1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return helper(weights, values, n, capacity, dp);
}

private int helper(int[] weights, int[] values, int n, int capacity, int[][] dp) {
    if (n == 0 || capacity == 0) return 0;
    if (dp[n][capacity] != -1) return dp[n][capacity];

    if (weights[n-1] > capacity) {
        dp[n][capacity] = helper(weights, values, n-1, capacity, dp);
    } else {
        int include = values[n-1] + helper(weights, values, n-1, capacity - weights[n-1], dp);
        int exclude = helper(weights, values, n-1, capacity, dp);
        dp[n][capacity] = Math.max(include, exclude);
    }
    return dp[n][capacity];
}

Time Complexity: O(N × W)
Space Complexity: O(N × W)

6. Bottom-Up Dynamic Programming (Tabulation)

public int knapsackBottomUp(int[] weights, int[] values, int n, int capacity) {
    int[][] dp = new int[n+1][capacity+1];

    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0) dp[i][w] = 0;
            else if (weights[i-1] <= w) {
                dp[i][w] = Math.max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][capacity];
}

Time Complexity: O(N × W)
Space Complexity: O(N × W)

7. Space Optimization

Since only the previous row is needed:

public int knapsackOptimized(int[] weights, int[] values, int n, int capacity) {
    int[] dp = new int[capacity+1];

    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    return dp[capacity];
}

Space Complexity: O(W)

8. Variants of 0/1 Knapsack Pattern

  1. Subset Sum Problem – Check if subset sum equals target → weights = values
  2. Count of Subsets with Given Sum
  3. Minimum Subset Difference – Split array into two subsets to minimize difference
  4. Target Sum – Find number of ways to assign +/− signs to reach target

Observation:

  • All these problems are decision-making problems with constraints → 0/1 Knapsack DP pattern applies.

9. Tips and Observations

  1. Identify decision for each item: include or exclude.
  2. DP state can be (index, remaining capacity).
  3. Use memoization for top-down and tabulation for bottom-up.
  4. Space can often be reduced to O(W) by iterating from right to left.
  5. Many subset and partition problems can be reduced to 0/1 Knapsack.

10. Common Edge Cases

  • Capacity = 0 → Maximum value = 0
  • No items → Maximum value = 0
  • Items heavier than capacity → Excluded automatically
  • Negative weights or values → Typically not allowed in standard 0/1 Knapsack

11. Key Takeaways

  1. 0/1 Knapsack is a decision-making DP pattern: include or exclude each item.
  2. Core DP relation: dp[i][W] = max(include, exclude)
  3. Approaches:
    • Recursive → O(2^N)
    • Top-down with memoization → O(N × W)
    • Bottom-up tabulation → O(N × W)
    • Space-optimized → O(W)
  4. Many subset, partition, and sum problems are variants of 0/1 Knapsack.
  5. Recognize the pattern when the problem involves selection under constraints.