Dynamic Programming7 min read

Unbounded Knapsack

Take as many of each item as you want — the vending machine version
time:Pseudo-poly · \(O(n·W)\)space:\(O(W)\)key difference:iterate capacity forward, not backward

Picture a vending machine stocked with snacks. You have a budget, and you can buy any snack as many times as you want — there's no limit per item. You're trying to maximize how much you get for your money. That's Unbounded Knapsack.

Compare this to 0/1 Knapsack, where each item is unique (like packing a suitcase — you only have one jacket). Here, the supply is unlimited. That one difference completely changes the DP update direction.

The One-Direction Flip

In 0/1 Knapsack, we iterated capacity from right to left to prevent reusing an item. In Unbounded Knapsack, we want reuse — so we iterate left to right. When we compute dp[cap], dp[cap - wt[i]] has already been updated in the current pass, which means item i could have been used again. That's exactly what we want.

Recurrence: dp[cap] = max(dp[cap], dp[cap - wt[i]] + val[i]) for each item i, iterating cap from wt[i] to W.

Coin Change — Minimum Coins

Given coin denominations, what's the fewest coins to make a target amount? This is unbounded knapsack where each "item" is a coin, its "weight" is its value, and you're minimizing count instead of maximizing value. dp[amount] = min over all coins c of (dp[amount - c] + 1). Initialize dp[0] = 0, dp[w] = ∞ for w > 0.

Coin Change 2 — Count the Ways

How many distinct combinations of coins make the amount? dp[w] += dp[w - c] for each coin c. But be careful: put coins in the outer loop and amounts in the inner loop. This counts combinations (where [1,2] and [2,1] are the same thing). Flipping the loops would count permutations instead.

Rod Cutting

A rod of length n can be cut and sold in pieces. Each piece length has a price. Maximize revenue. Every cut length is a reusable "item" — this is pure unbounded knapsack. dp[l] = max over all cut lengths c of (price[c] + dp[l - c]).

Note: The only difference between 0/1 and Unbounded Knapsack is one word in the inner loop: 'range(W, w-1, -1)' becomes 'range(w, W+1)'. Left-to-right allows reuse. Right-to-left prevents it.

Coin Change — minimum coins

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for w in range(coin, amount + 1):  # left to right!
            dp[w] = min(dp[w], dp[w - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1


print(coin_change([1, 5, 10], 12))  # 3  (10+1+1)
print(coin_change([2], 3))          # -1 (impossible)
Output
3
-1

Complexity

⏱️ Timen item types × W capacity values; same as 0/1 knapsack
Pseudo-polynomial\(O(n·W)\)
📦 SpaceOnly needs 1D — no 2D table required even for reconstruction
Single array\(O(W)\)
🔄 vs 0/1 KnapsackUnbounded naturally stays 1D; reconstruction also only needs 1D array
Same time, less space\(O(W)\) vs \(O(n·W)\)
🪙 Coin Change 2 (count ways)Coins outer loop, amounts inner — ensures combinations not permutations
Pseudo-polynomial\(O(n·W)\)

Quick check

Why do we iterate capacity left to right in unbounded knapsack — the opposite of 0/1?

Continue reading

0/1 Knapsack
Pack a suitcase for maximum value — each item is all-or-nothing
→
1D DP
Build the answer one step at a time — just like climbing stairs
→