DPAlgorithmaka complete knapsack, knapsack with repetition, rod cutting

Unbounded Knapsack

Maximize value under a capacity when every item may be taken any number of times — the 0/1 loop run forward.

▶ VisualizePattern: Dynamic ProgrammingPractice (3)
Progress

Overview

Same setup as 0/1 Knapsack — weights, values, capacity W — but each item type is available in unlimited supply. The optimal solution may contain the same item many times. Rod cutting (cut a rod of length n into pieces with given prices to maximize revenue) and "minimum coins to make change" (Coin Change) are instances.

The DP is one line different from 0/1: the state loses the "first i items" dimension (or, equivalently, the inner capacity loop runs upward), because after taking an item you are allowed to consider it again.

1D DPknapsackrepetition allowedO(n·W)rod cutting

Intuition

A mental model before the formal terms.

Rod cutting with prices p[1..4] = {1, 5, 8, 9} for lengths 1..4 and a rod of length 4. Options: no cut (9), 1+3 (1+8 = 9), 2+2 (5+5 = 10), 1+1+2 (1+1+5 = 7), four 1s (4). Best is 2+2 = 10 — the same piece used twice, which the 0/1 model forbids.

Think of filling capacity c by choosing the *last* item placed. Whatever it is, the remainder c - w must itself be filled optimally, and that remainder is free to use the same item again. So dp[c] looks at dp[c - w] from the current state of the array, not the previous row.

How it works

  1. State: dp[c] = maximum value achievable with total weight ≤ c using any number of copies of each item.
  2. Transition: dp[c] = max over items i with w[i] ≤ c of dp[c - w[i]] + v[i] (and dp[c] itself, for "at most"). The 2D form is dp[i][c] = max(dp[i-1][c], dp[i][c - w[i]] + v[i]) — note dp[i], not dp[i-1], in the take branch.
  3. Base case: dp[0] = 0. For "exactly c", set dp[c>0] = -∞ initially.
  4. Iteration order: item-outer, capacity-inner ascending from w[i] to W; or capacity-outer, item-inner. Both work because dp[c - w] is finished before dp[c] either way. Item-outer is preferred when the number of *combinations* is being counted (it avoids counting orderings).
  5. Answer location: dp[W].
  6. Space optimization: already 1D. The i dimension is unnecessary because reuse is allowed, so the "previous row" distinction disappears.

Why it works

Optimal substructure: take any optimal multiset for capacity c and remove one copy of some item i in it. What remains is a multiset of weight ≤ c - w[i], and it must be optimal for that capacity — otherwise replacing it with a better one (plus item i again) would beat the assumed optimum. Hence the max over all possible "last items" is exact.

Ascending iteration is correct precisely because dp[c - w[i]] may already include item i; that is allowed, so reading the updated value is the intended semantics. The 0/1 version needs the descending loop to *prevent* this.

The item-outer ordering computes, for each prefix of items, the best value using only those items with repetition; by induction over items the final array is optimal over all items.

Recognition

How to tell a problem wants this.

  • "Unlimited supply", "as many as you want", "any number of times", "infinite coins".
  • Cutting/partitioning a length or amount into pieces with given prices or costs.
  • Combination counting: "how many ways to make amount A from denominations" — item-outer unbounded knapsack with +=.
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

2/3
0
3/5
1
5/9
2
0123456789
0000000000
1/22A single row suffices because each item may be used any number of times: dp[c] may depend on dp[c - w] from the same row. Start with all zeros.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Unbounded Knapsack →
1dp[0..W] = 0
2for c in 1 .. W:
3  for each item i with w[i] <= c:
4    dp[c] = max(dp[c], dp[c-w[i]] + v[i])
5return dp[W]
Variables
W9
Complexity
best O(n·W)
avg O(n·W)
worst O(n·W)
space O(W)
Speed

Pseudocode

1dp = array[W + 1] filled with 0
2for i in 0..n-1:
3  for c from w[i] up to W:
4    dp[c] = max(dp[c], dp[c - w[i]] + v[i])
5return dp[W]

Implementations

1# dp[c] = best value with total weight <= c, unlimited copies of each item
2def unbounded_knapsack(weights: list[int], values: list[int], W: int) -> int:
31 · State table
4    dp = [0] * (W + 1)
52 · Base cases
6    dp[0] = 0  # nothing fits in capacity 0
73 · Transition
8    for w, v in zip(weights, values):
9        for c in range(w, W + 1):          # ASCENDING: dp[c - w] may already include this item
10            dp[c] = max(dp[c], dp[c - w] + v)
114 · Answer
12    return dp[W]
13 
14 
15# Rod cutting: prices[k] is the price of a piece of length k + 1
16def rod_cutting(prices: list[int], n: int) -> int:
17    dp = [0] * (n + 1)
18    for length in range(1, n + 1):
19        for cut in range(1, min(length, len(prices)) + 1):
20            dp[length] = max(dp[length], prices[cut - 1] + dp[length - cut])
21    return dp[n]
Walkthrough
  1. dp = [0] * (W + 1) is the whole state; a flat list of ints has no aliasing issue.
  2. Base case dp[0] = 0.
  3. zip(weights, values) pairs items; range(w, W + 1) ascends so the item can be reused within the same pass.
  4. rod_cutting bounds the cut with min(length, len(prices)) so it never indexes past the price list.
Complexity (this implementation)
time O(n·W) · space O(W)

Exact for any magnitude; pure-Python loops are ~50x slower than C++, so W·n around 10^7 is the practical limit.

Language notes
  • For "exactly W" use float("-inf") as the sentinel; it compares correctly with ints in max.
  • lru_cache on a closure over cap is the top-down form; recursion depth is W / min_weight, which can exceed the default limit.
  • Loop order (items outer vs capacity outer) does not change the result here — unlike counting combinations vs permutations.
Common mistakes in this language
  • Using range(W, w - 1, -1) (the 0/1 loop) — items can then be used only once.
  • Starting at range(0, W + 1): dp[c - w] with a negative index silently wraps to the end of the list in Python.
  • Deep recursion in the memoized version for small weights and large W.
Language differences that matter here
  • Negative index reads: C++ is undefined behaviour, JS/TS return undefined (→ NaN), Python wraps to the end of the list — all wrong, only Python is silent about it being "valid".
  • Sentinel for "exactly W": -Infinity in JS/TS, float("-inf") in Python, LLONG_MIN / 2 in C++ (a full LLONG_MIN overflows when a value is added).
  • Overflow: C++ needs long long; JS/TS are exact below 2^53; Python is exact.

Complexity

Best
O(n·W)
Average
O(n·W)
Worst
O(n·W)
Space
O(W)

Pseudo-polynomial in W. No 2D table is ever needed.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Items or denominations with unlimited supply and an integer capacity/amount.
  • Rod cutting, integer partition with weights, "min/max/count of ways to make a total from reusable parts".
  • Coin change in both forms: minimum coins (min-plus) and number of combinations (sum, item-outer loop).
Avoid it when
  • Each item has a limited count — use 0/1 Knapsack or bounded knapsack with binary splitting.
  • Capacity is enormous relative to n — the table is infeasible; look for greedy structure (canonical coin systems) or number-theoretic shortcuts.
  • You need *ordered* sequences (permutations) that sum to a total — swap to capacity-outer, item-inner loop (Combination Sum IV), which is a different count.

Alternatives

0/1 KnapsackCoin ChangeFractional Knapsack

Common mistakes

  • Iterating capacity downward — that makes it 0/1 knapsack and forbids repetition.
  • Mixing up the loop order in counting variants: item-outer counts combinations, capacity-outer counts permutations. They differ (for {1,2} and amount 3: 2 combinations, 3 permutations).
  • Initializing "exact amount" variants with 0 instead of -∞/+∞, which lets impossible capacities contribute.

Interview patterns

  • Coin Change II: number of combinations — dp[a] += dp[a - coin], coins outer loop.
  • Rod Cutting: maximize revenue over cut lengths.
  • Perfect Squares: minimum number of squares summing to n — unbounded min-plus with items 1, 4, 9, ….
  • Integer Break: maximize product of parts — unbounded knapsack with multiplication.
Interview questions on this
Mock interviews

Example problems

Combination SummediumCoin ChangemediumWord Breakmedium