Unbounded KnapsackUnbounded knapsack

01Why it exists

Reach for it when you see:Unlimited supply of each item, items that may be picked again, reaching a given total, the fewest items, the most value, how many combinations, making change, cutting stock, Coin Change.

02The core idea

In the 0/1 knapsack every item is either taken or left; in the unbounded knapsack you may take as many copies of an item as you like. The most direct idea is to enumerate how many copies of each item you take: dp[i][w] = max(dp[i−1][w − k·wᵢ] + k·vᵢ) for k from 0 to ⌊w / wᵢ⌋, which costs an extra loop. The key observation is that "take k copies" is the same as "take k−1 copies, then take one more", and that after taking a copy item i is still available, so the transition collapses to dp[i][w] = max(dp[i−1][w], dp[i][w−wᵢ] + vᵢ). Compared with the 0/1 knapsack, the only difference is that the "take it" branch reads dp[i] rather than dp[i−1].

Once the table is squeezed into a one-dimensional array, that difference becomes the direction of the inner loop. With items on the outside and w running upwards on the inside, dp[w−wᵢ] has already been updated this round by the time you compute dp[w], so it is exactly dp[i][w−wᵢ]: it may already contain item i, and adding another copy is reuse. Why that is correct: induct on w. The best solution for capacity w either uses no copy of item i at all, which is the old value this round has not touched yet, or it uses at least one; take one copy away and what is left must be the best solution for capacity w−wᵢ over the same items, and that cell is smaller than w, so it is already final. The 0/1 knapsack sweeps downwards precisely so that dp[w−wᵢ] keeps last round's value and no single item is taken twice.

Cost: with n kinds of item and capacity W, each item sweeps W once, so the time is O(nW) and the one-dimensional array takes O(W) space, with no best or worst case to distinguish. Asking for the fewest items or for the number of ways changes only the operation inside the transition, not the complexity. Note that this is pseudo-polynomial: the running time is proportional to the value of W, not to the number of bits in the input, so at W = 10⁹ you cannot even allocate the array. To recover which items were chosen, keep one more O(W) array recording which item updated each cell.

Three common mistakes. The first is the initial values: for the most value within a capacity of W, start everything at 0; for the fewest items hitting the total exactly, set dp[0] = 0 and everything else to ∞, or amounts that cannot be made will read as 0; and for the number of ways, set dp[0] = 1. The second is the loop order when counting: items outside and amount inside counts combinations (LeetCode 518), because each item is only ever considered in its own round, which pins the order down; amount outside and items inside counts permutations (LeetCode 377). For a maximum or a minimum the two orders agree — only counting tells them apart. The third is overflow in C++, where the intermediate counts can be far larger than the final answer. How this relates to the Coin Change (Greedy) lesson: greedy is only correct for well-behaved currency systems, while the unbounded knapsack is the general solution that works for any denominations. And the bounded knapsack, where each item has a limited supply, splits that supply into bundles of 1, 2, 4, … plus the remainder, turning the problem back into a 0/1 knapsack.

03The algorithm

1. 1Check the shape of the problem: every item may be used repeatedly, and you have to reach, or stay within, some total W. Define dp[w] as the best value, or the number of ways, at total w.
2. 2Set the initial values to match the goal: for the most value within W, all zeros; for the fewest items hitting W exactly, dp[0] = 0 and everything else ∞; for the number of ways, dp[0] = 1 and everything else 0.
3. 3Loop over the items on the outside and over w on the inside, running upwards from wᵢ to W: use dp[w] = max(dp[w], dp[w−wᵢ] + vᵢ) for the most value, min(dp[w], dp[w−wᵢ] + 1) for the fewest items, and dp[w] += dp[w−wᵢ] for the number of ways.
4. 4If the question really wants permutations (a different order counting as a different answer), swap the two loops: w runs from 1 to W on the outside and the items on the inside, transitioning only when wᵢ ≤ w.
5. 5The answer is in dp[W]. In the exact-total version, dp[W] still holding ∞ means the total cannot be made, so return −1. When counting in C++, switch to unsigned long long.

04Interactive demo

Coins [1, 2, 5] and an amount of 11, looking for the fewest coins. "Unbounded (forward sweep)" gives each coin one round and sweeps the amount from small to large; "0/1 knapsack (reverse sweep)" uses exactly the same transition but sweeps the amount from large to small, which amounts to having one coin of each kind. Blue is the cell being filled in, a grey ∞ is an amount that cannot be made yet, and the source cell dp[w−coin] is green while it still holds last round's value and amber once this round has updated it — that amber is the same coin being used a second time. Watch where the amber shows up in the forward mode, and how the two modes finish with dp[11] at 3 and at ∞ respectively.

05Code

The unbounded knapsack for maximum value, plus the two variants that come up most often: the fewest coins, and the number of ways in both its combination and its permutation form. The two counting versions sit side by side so that swapping the loops can be seen to compute genuinely different things. The C++ counting functions use unsigned long long to absorb the overflow in the intermediate values.

# Unbounded knapsack: unlimited copies of every item. dp[w] = best value for capacity at most w
# The only difference from 0/1: the inner loop becomes range(cap, wt - 1, -1), sweeping backwards
def unbounded_knapsack(weights, values, cap):
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):       # outer loop: the items
        for w in range(wt, cap + 1):           # inner loop forwards: dp[w - wt] may already use this item
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[cap]


# Fewest coins (LeetCode 322): the total must be hit exactly, so unreachable amounts start at INF
def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1


# Combinations (LeetCode 518): coins outside, amount inside, so 1+2 and 2+1 count as one
def count_combinations(coins, amount):
    dp = [1] + [0] * amount                    # there is one way to make 0: take nothing
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]


# Permutations (LeetCode 377): swap the loops, and 1+2 and 2+1 count as two
def count_permutations(nums, target):
    dp = [1] + [0] * target
    for a in range(1, target + 1):             # outer loop: the amount
        for x in nums:                         # inner loop: which item goes last
            if x <= a:
                dp[a] += dp[a - x]
    return dp[target]


if __name__ == "__main__":
    # A 10 m bar, sold as 3 m, 4 m and 5 m pieces for 260, 340 and 420
    print(unbounded_knapsack([3, 4, 5], [260, 340, 420], 10))  # 860 (3 + 3 + 4)
    print(coin_change([1, 2, 5], 11))          # 3 (5 + 5 + 1)
    print(coin_change([7, 10, 25], 63))        # 6 (25 + 10 + 7 × 4)
    print(coin_change([5, 10], 3))             # -1
    print(count_combinations([6, 10, 24], 120))  # 16
    print(count_permutations([6, 10, 24], 120))  # 39614

06Practice

• LeetCode 322Coin Change (fewest items, initialise to ∞)Medium
• LeetCode 518Coin Change II (combinations, coins on the outside)Medium
• LeetCode 279Perfect Squares (the items are 1, 4, 9, …)Medium
• LeetCode 377Combination Sum IV (permutations, loops swapped)Medium
• LeetCode 139Word Break (words can be reused and order matters)Medium
• LeetCode 1449Form Largest Integer With Digits That Add up to Target (hit the total exactly, then compare digit counts)Hard