0/1 Knapsack Problem

From matching strings to choosing gear

In Longest Common Subsequence, you used a 2D DP table to decide whether characters should align or be skipped.

Now we’ll use the same choose/skip instinct for a classic optimization problem: 0/1 Knapsack.

Imagine packing for an anime convention raid: each item has a weight and a value, but your bag has limited capacity. Which items should you bring to maximize total value?

This lesson matters because 0/1 Knapsack is a template for many interview problems involving:

• limited resources
• binary choices
• maximizing or minimizing value
• overlapping subproblems

Problem statement

You are given:

• weights[i]: weight of item i
• values[i]: value of item i
• capacity: maximum total weight allowed

Return the maximum total value you can carry.

Example:

item weight value 0 2 3 1 3 4 2 4 5 3 5 8

Capacity: 8

A valid choice is items 1 and 3: weight 3 + 5 = 8, value 4 + 8 = 12.

The 0/1 part means an item is either taken or not taken. No fractions, no duplicates.

For a bottom-up 0/1 Knapsack table, which DP state is most natural?

The two choices

For each item, there are only two possibilities:

1. Skip it
2. Take it, if it fits

Let:

dp[i][c] = best value using first i items with capacity c

For item i - 1 with weight w and value v:

skip = dp[i - 1][c]
take = v + dp[i - 1][c - w]

So:

if w > c:
    dp[i][c] = dp[i - 1][c]
else:
    dp[i][c] = max(skip, take)

This should feel familiar from LCS: each cell asks, “What smaller decisions already tell me the answer?”

In 0/1 Knapsack, each item can be selected at most ____.

Top-down version

Since you already practiced memoization in Fibonacci Series and LCS, the recursive version should look natural.

Define a function:

best_from(i, remaining)

It returns the best value we can get starting at item i with remaining capacity.

```python
from functools import lru_cache

weights = [2, 3, 4, 5]
values = [3, 4, 5, 8]
capacity = 8

@lru_cache(None)
def best_from(i, remaining):
    if i == len(weights) or remaining == 0:
        return 0

    # Option 1: skip current item
    best = best_from(i + 1, remaining)

    # Option 2: take current item, if it fits
    if weights[i] <= remaining:
        take = values[i] + best_from(i + 1, remaining - weights[i])
        best = max(best, take)

    return best

print("Best value:", best_from(0, capacity))
print("Cache stats:", best_from.cache_info())
```

True or false: when we take an item in 0/1 Knapsack, the remaining capacity decreases by that item’s weight.

Bottom-up version

Now we build the table directly.

Rows represent how many items are available. Columns represent capacity from 0 to capacity.

The base row and base column are 0 because:

• with 0 items, value is 0
• with capacity 0, value is 0

Then every later cell applies the skip/take recurrence.

```python
weights = [2, 3, 4, 5]
values = [3, 4, 5, 8]
capacity = 8
n = len(weights)

dp = [[0] * (capacity + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    w = weights[i - 1]
    v = values[i - 1]

    for c in range(capacity + 1):
        skip = dp[i - 1][c]

        if w <= c:
            take = v + dp[i - 1][c - w]
            dp[i][c] = max(skip, take)
        else:
            dp[i][c] = skip

print("Max value:", dp[n][capacity])
print("DP table:")
for i, row in enumerate(dp):
    print(f"{i} items:", row)
```

Space compression

The 2D table is clear, but each row only depends on the previous row.

So we can compress to one list:

dp[c] = best value achievable with capacity c so far

Important detail: for 0/1 Knapsack, scan capacities downward. That prevents the current item from being used more than once in the same iteration.

```python
weights = [2, 3, 4, 5]
values = [3, 4, 5, 8]
capacity = 8

dp = [0] * (capacity + 1)

for idx, (w, v) in enumerate(zip(weights, values)):
    for c in range(capacity, w - 1, -1):
        dp[c] = max(dp[c], v + dp[c - w])
    print(f"After item {idx} (w={w}, v={v}):", dp)

print("Max value:", dp[capacity])
```

In the one-row 0/1 Knapsack version, what can go wrong if capacities are scanned upward from small to large?

What you now own

0/1 Knapsack adds a powerful DP pattern to your toolkit:

• State includes an item boundary and a resource limit
• Each item creates a skip/take decision
• The recurrence compares the best value from both choices
• Tabulation runs in O(n * capacity) time
• The 2D table uses O(n * capacity) space
• The one-row version reduces space to O(capacity)

The core mental move is simple but deep: turn a big optimization problem into many smaller “best possible value under this limit” questions.

Next, we’ll shift from choosing items to choosing the best order of operations in Matrix Chain Multiplication.