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:

Code

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:

Code

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:

Code

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:

Code

         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:

Code

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):

Code

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

Complete Recurrence #

Code

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 #

Code

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):

Code

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:

Code

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:

Code

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!

Code

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:

Code

// 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:

Code

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

Code

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:

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

Summary: Day 40 Complete! #

We've mastered four 2D DP problems:

Unique Paths: Grid traversal (additive recurrence)
Longest Common Subsequence: Sequence comparison (conditional recurrence)
Edit Distance: Sequence transformation (three-way choice)
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!