Problem: 0/1 Knapsack

Our final 2D problem introduces selection under constraints: choosing items to maximize value while respecting capacity limits.

Problem Statement

Given n items, where each item i has:

• Weight: weights[i]
• Value: values[i]

And given a knapsack with capacity W, select items to:

• Maximize total value
• Without exceeding capacity W

Constraint: Each item can be used at most once (0/1: either take it or leave it).

Example 1:

Input:
  weights = [1, 2, 3]
  values  = [6, 10, 12]
  capacity = 5

Output: 22

Explanation:
  Take item 1 (weight=2, value=10)
  Take item 2 (weight=3, value=12)
  Total weight: 2 + 3 = 5 ≤ 5 ✓
  Total value: 10 + 12 = 22 (maximum possible)

Example 2:

Input:
  weights = [1, 3, 4, 5]
  values  = [1, 4, 5, 7]
  capacity = 7

Output: 9

Explanation:
  Take item 2 (weight=4, value=5)
  Take item 3 (weight=3, value=4)
  Total weight: 4 + 3 = 7 ≤ 7 ✓
  Total value: 5 + 4 = 9

  (Alternative: Take item 3 (weight=5, value=7) and item 0 (weight=1, value=1) → value=8, worse)

Why Greedy Fails

Greedy by value-to-weight ratio:

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
capacity = 7

Ratios: [1.0, 1.33, 1.25, 1.4]

Greedy picks:
  Item 3 (ratio=1.4, weight=5, value=7) → Remaining capacity: 2
  Item 0 (ratio=1.0, weight=1, value=1) → Remaining capacity: 1
  Total value: 8

Optimal picks:
  Item 1 (weight=3, value=4)
  Item 2 (weight=4, value=5)
  Total value: 9 > 8

Greedy doesn't work! We need DP.

Step 1: Define the State

What should dp[i][w] represent?

Definition: dp[i][w] = maximum value using the first i items with capacity w

Interpretation:

• i: Considering items 0 through i-1 (0-indexed)
• w: Current weight capacity
• Value: Best we can do with these items and this capacity

Answer: dp[n][W] where n = number of items, W = knapsack capacity

Step 2: Identify Base Cases

dp[0][w] for all w: No Items

If we have no items, value is 0 regardless of capacity.

dp[0][w] = 0 for all w

dp[i][0] for all i: No Capacity

If capacity is 0, we can't take any items, so value is 0.

dp[i][0] = 0 for all i

Base case summary:

         w=0  w=1  w=2  w=3  w=4  w=5
    i=0   0    0    0    0    0    0
    i=1   0    ?    ?    ?    ?    ?
    i=2   0    ?    ?    ?    ?    ?
    i=3   0    ?    ?    ?    ?    ?

Entire first row and first column are 0.

Step 3: Find the Recurrence Relation

For dp[i][w], we're deciding whether to include item i-1 (the i-th item, 0-indexed).

Two options:

Option 1: Don't Take Item i-1

If we skip item i-1:

• Value from item i-1: 0
• Best value: Using first i-1 items with capacity w
• Total: dp[i-1][w]

Option 2: Take Item i-1

Can we even take it?

Constraint: weights[i-1] <= w (item must fit)

If we take item i-1:

• Value gained: values[i-1]
• Capacity used: weights[i-1]
• Remaining capacity: w - weights[i-1]
• Best with remaining capacity: dp[i-1][w - weights[i-1]]
• Total: values[i-1] + dp[i-1][w - weights[i-1]]

Choose the Better Option

If item fits:

dp[i][w] = max(dp[i-1][w],                          // Don't take
               values[i-1] + dp[i-1][w-weights[i-1]]) // Take

If item doesn't fit (weights[i-1] > w):

dp[i][w] = dp[i-1][w]  // Can't take, so skip

Complete Recurrence

if (weights[i - 1] <= w) {
    // Item fits: choose max of taking it or leaving it
    dp[i][w] = Math.max(dp[i - 1][w],
                        values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
    // Item doesn't fit: can't take it
    dp[i][w] = dp[i - 1][w];
}

Step 4: Implementation

public class Knapsack {
    public int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;

        // Create DP table
        // dp[i][w] = max value using first i items with capacity w
        int[][] dp = new int[n + 1][capacity + 1];

        // Base cases: first row and column already 0 (default)

        // Fill table
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                // Can we take item i-1?
                if (weights[i - 1] <= w) {
                    // Yes: choose max of taking or leaving
                    int dontTake = dp[i - 1][w];
                    int take = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                    dp[i][w] = Math.max(dontTake, take);
                } else {
                    // No: can't take it
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // Return answer
        return dp[n][capacity];
    }
}

Step 5: Trace Through an Example

Let's trace knapsack([1, 2, 3], [6, 10, 12], 5):

weights = [1, 2, 3]
values  = [6, 10, 12]
capacity = 5

Items:
  Item 0: weight=1, value=6
  Item 1: weight=2, value=10
  Item 2: weight=3, value=12

Initialize:

         w=0  w=1  w=2  w=3  w=4  w=5
    i=0   0    0    0    0    0    0
    i=1   0    ?    ?    ?    ?    ?
    i=2   0    ?    ?    ?    ?    ?
    i=3   0    ?    ?    ?    ?    ?

Fill row 1 (considering item 0: weight=1, value=6):

w=1: weights[0]=1 <= 1 ✓
  dontTake = dp[0][1] = 0
  take = values[0] + dp[0][1-1] = 6 + dp[0][0] = 6 + 0 = 6
  dp[1][1] = max(0, 6) = 6

w=2: weights[0]=1 <= 2 ✓
  dontTake = dp[0][2] = 0
  take = values[0] + dp[0][2-1] = 6 + dp[0][1] = 6 + 0 = 6
  dp[1][2] = max(0, 6) = 6

w=3: dp[1][3] = max(0, 6) = 6
w=4: dp[1][4] = max(0, 6) = 6
w=5: dp[1][5] = max(0, 6) = 6

         w=0  w=1  w=2  w=3  w=4  w=5
    i=0   0    0    0    0    0    0
    i=1   0    6    6    6    6    6
    i=2   0    ?    ?    ?    ?    ?
    i=3   0    ?    ?    ?    ?    ?

Fill row 2 (considering items 0-1: item 1 has weight=2, value=10):

w=1: weights[1]=2 > 1 ✗
  dp[2][1] = dp[1][1] = 6

w=2: weights[1]=2 <= 2 ✓
  dontTake = dp[1][2] = 6
  take = values[1] + dp[1][2-2] = 10 + dp[1][0] = 10 + 0 = 10
  dp[2][2] = max(6, 10) = 10

w=3: weights[1]=2 <= 3 ✓
  dontTake = dp[1][3] = 6
  take = values[1] + dp[1][3-2] = 10 + dp[1][1] = 10 + 6 = 16
  dp[2][3] = max(6, 16) = 16

w=4: weights[1]=2 <= 4 ✓
  dontTake = dp[1][4] = 6
  take = values[1] + dp[1][4-2] = 10 + dp[1][2] = 10 + 6 = 16
  dp[2][4] = max(6, 16) = 16

w=5: weights[1]=2 <= 5 ✓
  dontTake = dp[1][5] = 6
  take = values[1] + dp[1][5-2] = 10 + dp[1][3] = 10 + 6 = 16
  dp[2][5] = max(6, 16) = 16

         w=0  w=1  w=2  w=3  w=4  w=5
    i=0   0    0    0    0    0    0
    i=1   0    6    6    6    6    6
    i=2   0    6   10   16   16   16
    i=3   0    ?    ?    ?    ?    ?

Fill row 3 (considering items 0-2: item 2 has weight=3, value=12):

w=1: weights[2]=3 > 1 ✗
  dp[3][1] = dp[2][1] = 6

w=2: weights[2]=3 > 2 ✗
  dp[3][2] = dp[2][2] = 10

w=3: weights[2]=3 <= 3 ✓
  dontTake = dp[2][3] = 16
  take = values[2] + dp[2][3-3] = 12 + dp[2][0] = 12 + 0 = 12
  dp[3][3] = max(16, 12) = 16

w=4: weights[2]=3 <= 4 ✓
  dontTake = dp[2][4] = 16
  take = values[2] + dp[2][4-3] = 12 + dp[2][1] = 12 + 6 = 18
  dp[3][4] = max(16, 18) = 18

w=5: weights[2]=3 <= 5 ✓
  dontTake = dp[2][5] = 16
  take = values[2] + dp[2][5-3] = 12 + dp[2][2] = 12 + 10 = 22
  dp[3][5] = max(16, 22) = 22

Final table:

         w=0  w=1  w=2  w=3  w=4  w=5
    i=0   0    0    0    0    0    0
    i=1   0    6    6    6    6    6
    i=2   0    6   10   16   16   16
    i=3   0    6   10   16   18   22

Return dp[3][5] = 22 ✓

Maximum value is 22: Take items 1 and 2 (weights 2+3=5, values 10+12=22).

Reconstructing the Selection

Which items were selected?

Backtracking approach:

public List<Integer> getSelectedItems(int[] weights, int[] values, int[][] dp, int capacity) {
    List<Integer> selected = new ArrayList<>();
    int i = weights.length;
    int w = capacity;

    while (i > 0 && w > 0) {
        // Was item i-1 taken?
        if (dp[i][w] != dp[i - 1][w]) {
            // Yes: value changed, so item i-1 was taken
            selected.add(i - 1);
            w -= weights[i - 1];  // Reduce capacity
            i--;
        } else {
            // No: value didn't change, skip this item
            i--;
        }
    }

    Collections.reverse(selected);  // Items were added in reverse order
    return selected;
}

Trace for our example:

Start: i=3, w=5, dp[3][5]=22

dp[3][5]=22 != dp[2][5]=16 → Item 2 taken
  selected = [2]
  w = 5 - 3 = 2
  i = 2

dp[2][2]=10 != dp[1][2]=6 → Item 1 taken
  selected = [2, 1]
  w = 2 - 2 = 0
  i = 1

w = 0, stop

selected = [2, 1] → Reverse: [1, 2]

Items 1 and 2 (0-indexed) were selected ✓

Complexity Analysis

Time Complexity: O(n × W)

• Two nested loops: n items × W capacity
• Each cell: O(1) work
• Total: O(n × W)

Note: This is pseudo-polynomial because W is not polynomial in the input size (W could be huge!). For small W, very efficient.

Space Complexity: O(n × W)

• DP table of size (n+1) × (W+1)
• Total: O(n × W)

Space Optimization

Observation: To compute row i, we only need row i-1.

But there's a catch: We read from dp[i-1][w - weights[i-1]], which is to the left of current position.

Solution: Iterate right-to-left in the inner loop!

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

    for (int i = 0; i < n; i++) {
        // Iterate RIGHT-TO-LEFT to avoid overwriting needed values
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }

    return dp[capacity];
}

Why right-to-left?

When computing dp[w], we need dp[w - weights[i]] from the previous iteration.

If we go left-to-right: We might overwrite dp[w - weights[i]] before using it!

If we go right-to-left: We use dp[w - weights[i]] (old value from previous iteration) before updating dp[w].

Space complexity: O(W) instead of O(n × W)!

0/1 vs Unbounded Knapsack

Key difference:

0/1 Knapsack (today's problem):

• Each item can be used at most once
• Recurrence: dp[i][w] depends on dp[i-1][...] (previous items only)

Unbounded Knapsack (like Coin Change from Day 39):

• Each item can be used unlimited times
• Recurrence: dp[i][w] depends on dp[i][...] (can reuse same item)

Example of unbounded:

// Unbounded: Can use same item multiple times
for (int i = 0; i < n; i++) {
    for (int w = weights[i]; w <= capacity; w++) {
        dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        // Notice: dp[w - weights[i]] might already include item i!
    }
}

Direction: Left-to-right for unbounded (reuse item), right-to-left for 0/1 (use once).

Variations

Variation 1: Subset Sum

Problem: Can we select items with total weight exactly equal to target?

Example:

• nums = [3, 34, 4, 12, 5, 2]
• target = 9

Answer: Yes (4 + 5 = 9)

DP approach:

boolean[] dp = new boolean[target + 1];
dp[0] = true;  // Can make 0 with no items

for (int num : nums) {
    for (int w = target; w >= num; w--) {
        dp[w] = dp[w] || dp[w - num];
    }
}

return dp[target];

This is 0/1 knapsack with:

• weights = values = nums
• Check if we can achieve exactly target weight
• Return boolean instead of max value

Variation 2: Partition Equal Subset Sum

Problem: Can we partition array into two subsets with equal sum?

Example: [1, 5, 11, 5] → Yes: {1, 5, 5} and {11}

Solution: Use subset sum!

If total sum is odd: Impossible (can't split evenly)

If total sum is even: Check if we can make sum/2

public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if (sum % 2 != 0) return false;

    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int num : nums) {
        for (int w = target; w >= num; w--) {
            dp[w] = dp[w] || dp[w - num];
        }
    }

    return dp[target];
}

This is the same knapsack pattern!

Variation 3: Target Sum

Problem: Assign +/- to each number to reach target sum.

Example: nums = [1, 1, 1, 1, 1], target = 3

Answer: 5 ways (-1+1+1+1+1, 1-1+1+1+1, etc.)

Transformation:

• Let P = subset assigned +
• Let N = subset assigned -
• P - N = target
• P + N = sum
• Solving: P = (target + sum) / 2

Problem becomes: Count subsets with sum P (0/1 knapsack counting variant!)

Key Takeaways

0/1 Knapsack demonstrates:

• Selection under constraints: Choose items to optimize value within capacity
• Binary choice: Take or leave each item
• Bounded usage: Each item used at most once
• Pseudo-polynomial time: Efficient for small capacities

Pattern Recognition:

This is a constrained selection problem where:

• State is (items considered, remaining capacity)
• Recurrence is binary choice (take or skip)
• Base cases are no items or no capacity

This pattern appears in:

• Subset Sum
• Partition Equal Subset Sum
• Target Sum
• Coin Change variants
• Job scheduling with dependencies

Knapsack is one of the most versatile DP patterns, with countless real-world applications.

Real-World Applications

Knapsack appears in:

1. Resource allocation: Limited budget, maximize return
2. Cargo loading: Limited weight, maximize value
3. Project selection: Limited time/money, maximize profit
4. Data compression: Limited space, maximize important data
5. Portfolio optimization: Limited capital, maximize returns

Summary: Day 40 Complete!

We've mastered four 2D DP problems:

1. Unique Paths: Grid traversal (additive recurrence)
2. Longest Common Subsequence: Sequence comparison (conditional recurrence)
3. Edit Distance: Sequence transformation (three-way choice)
4. 0/1 Knapsack: Constrained selection (binary choice)

Each represents a fundamental 2D pattern you'll see again and again.

Key skills learned:

• Setting up 2D DP tables correctly
• Identifying when problems need 2D state
• Formulating recurrences with multiple parameters
• Space optimization for 2D problems
• Reconstructing solutions from DP tables

The principles from 1D (Day 39) still apply: Define state, identify base cases, find recurrence, implement systematically.

2D DP just adds another dimension of complexity - but the thinking process remains the same!