Dynamic programming · recursion + memoization

What fits in the 0/1 knapsack?

Each item has a weight and a value. Pick a subset with total weight at most the bag’s capacity and the greatest possible value. Every item is a yes-or-no decision: take it once, or leave it.

Items: (weight, value)Capacity: 6Goal: maximum value

The recursive decision

Ask what the best remaining value is.

solve(i, remaining) means: the best value using items from index i onward with remaining weight available.

Skip item iorTake item i, if it fits

solve(i, c) = max(solve(i+1, c), value[i] + solve(i+1, c-weight[i]))

The take branch exists only when weight[i] ≤ c. When all items are considered, the answer is 0.

The reusable insight

Same question, same answer.

Different paths can reach the same pair (i, remaining). Plain recursion solves it again. Memoization stores its answer and returns it immediately next time.

Plain recursionO(2ⁿ) time

With memoizationO(n × C) time

Memo storageO(n × C) space

C is the integer capacity. Both approaches use O(n) call-stack space.

Interactive walkthrough

Follow the calls. Watch answers get cached.

Switch modes to see which repeated calls memoization avoids. Purple is the active call, green is solved, and gold is a cache hit.

Items · weight and value

Bag capacity 6

Ready

Press Next or Play

The first call asks for the best value from every item.

Calls made0

States solved0

Cache hits0

Recursion tree · skip then take

Calls appear here as you step forward.

Each indented pair is one recursive question. The number after → is its returned value.

Memo table · solved (item index, capacity)

A cell fills when its answer is saved.

Current callSaved answerCache hit

Best value—

Finish the walkthrough to reveal the chosen items.

Compare:

Step 0 / 0

Try items (weight:value, separated by commas)CapacityPlay speed

Python · plain recursion

Explore both choices.

The item index always advances, so an item can never be picked twice.

def knapsack(items, capacity):
    def solve(i, remaining):
        if i == len(items):
            return 0
        weight, value = items[i]
        skip = solve(i + 1, remaining)
        if weight > remaining:
            return skip
        take = value + solve(i + 1, remaining - weight)
        return max(skip, take)

    return solve(0, capacity)

Python · memoized recursion

Remember each state.

The two inputs to solve form the memo key. A repeated key returns the saved answer.

from functools import cache

def knapsack(items, capacity):
    @cache
    def solve(i, remaining):
        if i == len(items):
            return 0
        weight, value = items[i]
        skip = solve(i + 1, remaining)
        if weight > remaining:
            return skip
        take = value + solve(i + 1, remaining - weight)
        return max(skip, take)

    return solve(0, capacity)