The Unbounded Knapsack problem extends the classic knapsack by allowing you to pick an item multiple times instead of just once. The challenge is no longer just choosing which items to include, but also how many times to include each one to maximize value within a fixed capacity.

The formal difference:

This sounds like a small tweak, but it changes the structure of the solution. In 0/1 knapsack, once we decide to include item i, we move on to item i+1 with reduced capacity. In unbounded knapsack, after including item i, we can still consider item i again.

The loop in the unbounded version, where an item feeds back into itself, is the structural difference.

An unbounded knapsack problem typically shows these signals:

Common problem types that follow this pattern:

Keywords like "unlimited," "infinite supply," or "any number of times," or the absence of any reuse restriction, are the cue to think unbounded knapsack.

State Definition

For most unbounded knapsack problems, a 1D DP array suffices:

dp[w] = the optimal answer for capacity/target w

Because items can be reused freely, there is no need for a separate dimension tracking which items have been consumed.

Transition

For each capacity w, we try every item and pick the best result:

dp[w] = best of dp[w - item] for all valid items

What "best" means depends on the problem. For minimization (like Coin Change), it is min. For maximization (like rod cutting), it is max. For counting (like Coin Change II), it is sum.

The Critical Detail: Iteration Direction

Unbounded knapsack diverges from 0/1 knapsack in the direction of the capacity loop. In 0/1 knapsack with a 1D array, we iterate capacity backwards so dp[w - weight] reflects the state before the current item. In unbounded knapsack, we iterate capacity forwards so dp[w - weight] may already include the current item, which is exactly the reuse we want.

Outer Loop vs Inner Loop: Combinations vs Permutations

For optimization problems (min coins, max value), only the iteration direction matters: forward for reuse, backward for one-shot use. The order of the two loops (items outside, capacity inside, or the reverse) gives the same answer.

For counting problems, the loop order changes the answer. This is the most common bug in Coin Change II (LC 518).

Consider coins = [1, 2, 3], amount = 4. The valid combinations summing to 4 (order does not matter) are:

That is 4 combinations.

The valid permutations (order matters: 1 + 2 + 1 is different from 1 + 1 + 2) are:

That is 7 permutations.

Two loop orderings give two different DPs:

The intuition for why this works:

If the problem asks for combinations and you initially wrote the swapped order, swap the loops. The recurrence body does not change.

For optimization problems the loop order does not matter because min and max are commutative and associative, and counting double or single does not change the optimum. For sum-based counting, it does.

Problem Statement

Given an array coins representing coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. If it is not possible, return -1. You have an infinite supply of each coin.

Example:

Intuition

A classic unbounded knapsack minimization problem. We have unlimited coins (unbounded), a target amount (capacity), and we want to minimize the number of coins used.

Our DP state: dp[a] = minimum number of coins to make amount a.

Base case: dp[0] = 0 (zero coins needed to make amount 0).

Transition: for each amount a and each coin c, if c <= a, then dp[a] = min(dp[a], dp[a - c] + 1).

We initialize all other entries to a large value (like amount + 1) to represent "impossible." If dp[amount] is still this large value at the end, the answer is -1.

Step-by-Step Trace

Trace through coins = [1, 3, 4], amount = 6.

Initial state: dp = [0, INF, INF, INF, INF, INF, INF] where INF = 7 (amount + 1).

Final DP array: [0, 1, 2, 1, 1, 2, 2]

The answer is dp[6] = 2, which corresponds to using two coins of value 3.

At a=6, the coin 3 option uses dp[3], which itself was computed using coin 3. Coin 3 gets used twice, which is what we want in unbounded knapsack.

Implementation

Complexity Analysis

A note on pseudo-polynomial complexity

O(amount * n) is pseudo-polynomial*, not polynomial. The runtime depends on the numeric value of amount, not on its bit length. For amount = 10^4 the DP runs in milliseconds; for amount = 10^18 it is infeasible even though the input description is short.

Coin Change and Unbounded Knapsack are weakly NP-hard: the DP works only because typical constraints cap amount around 10^4-10^6. A common follow-up is "what if amount can be up to 10^12?" At that point the DP no longer fits and you would use BFS variants, meet-in-the-middle, or number-theoretic structure on the coin set.

The brute force recursive solution without memoization would be O(n^amount) in the worst case, since each amount branches into n choices and the recursion depth is bounded by amount / min(coins).