Dynamic programming · recursion + memoization

What fits in the unbounded knapsack?

Input: item types with positive integer weights and values, and an integer bag capacity. You may take any type as many times as you like. Find the maximum total value whose total weight does not exceed the capacity.

Items (weight:value): 2:5, 3:7, 4:9Capacity: 7Output: 17 (2 + 2 + 3 weight)

The recursive decision

Ask what the best remaining value is.

solve(i, remaining) means: the best value using item types from index i onward with remaining capacity.

Skip this type → i + 1orTake one → stay at i

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

Only take when weight[i] ≤ c. Taking reduces capacity but keeps the same index, so that type can be chosen again. No types left or no capacity means return 0.

The reusable insight

Same question, same answer.

Different paths can reach the same pair (i, remaining). Plain recursion repeats all its work. Memoization saves the best value for that pair and reuses it on the next visit.

Plain recursionExponential time

With memoizationO(n × C) time

Memo storageO(n × C) space

n is the number of item types and C is the integer capacity. The call stack is at most O(n + C) deep because each call either skips a type or reduces capacity.

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 7

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 advances, take repeats

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 item types (weight:value, separated by commas)CapacityPlay speed

Python · plain recursion

Explore both choices.

Skip advances to the next type. Take stays at i, allowing another copy. Positive weights ensure capacity eventually runs out.

def unbounded_knapsack(items, capacity):
    def solve(i, remaining):
        if i == len(items) or remaining == 0:
            return 0
        weight, value = items[i]
        skip = solve(i + 1, remaining)
        if weight > remaining:
            return skip
        take = value + solve(i, 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 unbounded_knapsack(items, capacity):
    @cache
    def solve(i, remaining):
        if i == len(items) or remaining == 0:
            return 0
        weight, value = items[i]
        skip = solve(i + 1, remaining)
        if weight > remaining:
            return skip
        take = value + solve(i, remaining - weight)
        return max(skip, take)

    return solve(0, capacity)