Unbounded Knapsack

The Unbounded Knapsack Problem (UKP) — also known as the Complete Knapsack or Integer Knapsack with Repetition — generalizes 01 Knapsack by removing the “each item used at most once” restriction: every item is available in unlimited supply, and we may take as many copies of any item as fit. Given n item types with positive integer weights w_i and values v_i, and a knapsack of integer capacity W, maximize total value subject to total weight ≤ W. The recurrence and table fill differ from 0/1 knapsack in one small but critical place — when reading the “smaller subproblem” for the take branch, we read dp[i][w - w_i] (same row, item still available) instead of dp[i-1][w - w_i] (previous row, item consumed). In the 1D rolling-array form this manifests as iterating capacity in ascending order, which is the opposite of 0/1 knapsack and the most common UKP bug. UKP is the abstract parent of the Coin Change family and the rod-cutting problem (CLRS Ch. 15.1).

1. Intuition — The All-You-Can-Pack Buffet

The 0/1 knapsack story is a hiker choosing among a fixed inventory of distinct objects: one tent, one sleeping bag, one stove. Each is a single physical item; you take it or leave it. The unbounded variant changes the picture from “fixed inventory” to “unlimited stockroom.” The hiker is now standing in a warehouse next to pallets of energy bars, identical bottles of water, and identical wool socks — there are as many of each as he could possibly want. The constraint is no longer about which copies exist; the constraint is purely about the backpack’s capacity.

Concretely: energy bars weigh 100 g each and provide 250 kcal each; water bottles weigh 500 g and provide 0 kcal but are required for survival (let’s pretend). With a 2 kg knapsack budget, how many bars and bottles maximize total kcal? The answer is “as many bars as fit” (20 bars × 250 = 5000 kcal). With more interesting trade-offs the answer becomes non-obvious and DP is required.

The unbounded knapsack arises naturally in many disguises:

Rod cutting (CLRS Ch. 15.1). A steel rod of length n can be cut into integer-length pieces, each with a market price p_i for length i. Maximize total revenue. Pieces are infinitely “available” (you cut as many length-3 pieces as you like from the rod, capped by total length); the rod length is the capacity.
Coin change — number of ways (LC 518; see Coin Change variant B). Each denomination is available unlimited times.
Coin change — minimum coins (LC 322; see Coin Change variant A). Same structure, min-aggregated instead of max-aggregated.
Cutting stock problem (Gilmore & Gomory 1961). The industrial origin: cutting raw material rolls into customer-requested widths to minimize waste.
Resource allocation with divisible-by-unit budgets, inventory planning with bulk-purchase discounts, etc.

The problem is weakly NP-hard (same complexity class as 0/1 knapsack), and the standard O(nW) DP is pseudo-polynomial — polynomial in n and the value of W, but exponential in the number of bits required to encode W (Garey & Johnson 1979, Computers and Intractability). For interview-sized inputs (W ≤ 10^4 or so) this is comfortably fast.

2. Tiny Worked Example

Items (1-indexed):

i	weight w_i	value v_i	density v_i / w_i
1	2	3	1.50
2	3	4	1.33
3	4	5	1.25

Capacity W = 7.

State: dp[i][w] = maximum value attainable using unlimited copies of items 1..i, total weight ≤ w.

Recurrence: for each item i and capacity w,

dp[i][w] = max( dp[i-1][w],                                # don't use item i at all
                dp[i  ][w - w_i] + v_i  if w_i ≤ w )       # take ONE more copy of item i

Note the subtle but critical difference from 01 Knapsack: the take branch reads dp[i][w - w_i] (same row i), not dp[i-1][w - w_i] (previous row). Reading the same row means “item i is still available for further use” — exactly the unbounded-supply property. In 0/1 knapsack the corresponding read is dp[i-1][·], which means “item i has been consumed, only items 1..i-1 remain.”

Base cases: dp[0][w] = 0 for every w (no items → no value); dp[i][0] = 0 (zero capacity → no value).

We fill the 2D table row by row, each row left-to-right.

After i = 0:

w →	0	1	2	3	4	5	6	7
i=0	0	0	0	0	0	0	0	0

After i = 1 (weight 2, value 3). For w < 2: only “don’t use” → 0. For w ≥ 2: take the larger of dp[0][w] = 0 and dp[1][w - 2] + 3 (same row, just-updated cells):

dp[1][2] = max(0, dp[1][0] + 3) = max(0, 3) = 3.
dp[1][3] = max(0, dp[1][1] + 3) = max(0, 3) = 3.
dp[1][4] = max(0, dp[1][2] + 3) = max(0, 6) = 6 ← already two copies of item 1!
dp[1][5] = max(0, dp[1][3] + 3) = max(0, 6) = 6.
dp[1][6] = max(0, dp[1][4] + 3) = max(0, 9) = 9 ← three copies.
dp[1][7] = max(0, dp[1][5] + 3) = max(0, 9) = 9.

w →	0	1	2	3	4	5	6	7
i=1	0	0	3	3	6	6	9	9

After i = 2 (weight 3, value 4). For w < 3: carry down. For w ≥ 3: max of dp[1][w] (don’t use item 2) and dp[2][w - 3] + 4:

dp[2][3] = max(3, dp[2][0] + 4) = max(3, 4) = 4.
dp[2][4] = max(6, dp[2][1] + 4) = max(6, 4) = 6.
dp[2][5] = max(6, dp[2][2] + 4) = max(6, 3 + 4) = 7.
dp[2][6] = max(9, dp[2][3] + 4) = max(9, 4 + 4) = 9 (three copies of item 1 still wins).
dp[2][7] = max(9, dp[2][4] + 4) = max(9, 6 + 4) = 10 (item 1 twice + item 2 once: weight 2+2+3=7, value 3+3+4=10).

w →	0	1	2	3	4	5	6	7
i=2	0	0	3	4	6	7	9	10

After i = 3 (weight 4, value 5). For w < 4: carry down. For w ≥ 4:

dp[3][4] = max(6, dp[3][0] + 5) = max(6, 5) = 6.
dp[3][5] = max(7, dp[3][1] + 5) = max(7, 5) = 7.
dp[3][6] = max(9, dp[3][2] + 5) = max(9, 3 + 5) = 9.
dp[3][7] = max(10, dp[3][3] + 5) = max(10, 4 + 5) = 10.

w →	0	1	2	3	4	5	6	7
i=3	0	0	3	4	6	7	9	10

Answer: dp[3][7] = 10. Achieved by 2 × item₁ + 1 × item₂ (weight 2+2+3=7, value 3+3+4=10). The greedy by density (item 1 has highest v/w = 1.5) would pick three copies of item 1 (weight 6, value 9), missing the optimum — greedy fails for UKP just as for 0/1.

3. Pseudocode

2D form (textbook):

dp[0..n][0..W] := all zeros
for i in 1..n:
    for w in 0..W:
        dp[i][w] = dp[i-1][w]                      # don't use item i
        if w_i <= w:
            dp[i][w] = max(dp[i][w], dp[i][w - w_i] + v_i)   # SAME row read
return dp[n][W]

1D rolling-array form (the canonical interview answer):

dp[0..W] := all zeros
for i in 1..n:
    for w in w_i..W:                # ASCENDING (opposite of 0/1 knapsack!)
        dp[w] = max(dp[w], dp[w - w_i] + v_i)
return dp[W]

The 1D form reuses the same array across all items. The inner loop runs from w_i upward so that when we compute dp[w], dp[w - w_i] already reflects the current item’s availability — exactly the “same row” semantics of the 2D recurrence. Iterating downward (as in 0/1 knapsack) would read dp[w - w_i] from the previous item’s row, defeating the unbounded property. This iteration-order distinction is the single sharpest difference between UKP and 0/1 KP.

4. Python Implementation

4.1 Top-Down (Memoization)

from functools import lru_cache
 
def unbounded_knapsack_topdown(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
 
    @lru_cache(maxsize=None)
    def dp(i: int, w: int) -> int:
        # Best value using items i..n-1 with capacity w.
        if i == n or w == 0:
            return 0
        # Choice 1: skip item i entirely (advance to i+1).
        best = dp(i + 1, w)
        # Choice 2: take ONE copy of item i, stay on i (allowing further copies).
        if weights[i] <= w:
            best = max(best, values[i] + dp(i, w - weights[i]))
        return best
 
    return dp(0, W)

The crucial line is dp(i, w - weights[i]) — not dp(i + 1, w - weights[i]). Staying on i allows the recursion to take another copy of item i next; advancing to i + 1 would commit us to “no more of i,” which is the 0/1 semantic. This is the recursive analogue of the same-row read in the tabulation.

State space: O(n · W). Per-state work: O(1). Total: O(nW).

4.2 Bottom-Up Tabulation — 2D

def unbounded_knapsack_2d(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]                # don't use
            if wi <= w:
                dp[i][w] = max(dp[i][w], dp[i][w - wi] + vi)   # SAME row
    return dp[n][W]

O(nW) time, O(nW) space. Note dp[i][w - wi] — same row i, just-updated value.

4.3 Bottom-Up Tabulation — 1D Rolling Array

def unbounded_knapsack_1d(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for wi, vi in zip(weights, values):
        for w in range(wi, W + 1):                 # ASCENDING — critical
            if dp[w - wi] + vi > dp[w]:
                dp[w] = dp[w - wi] + vi
    return dp[W]

O(nW) time, O(W) space. The inner loop’s ascending direction is the entire correctness argument for the 1D collapse: when we read dp[w - wi], it has already been updated under the current item, so the recurrence sees an “unlimited supply” of item i at smaller capacities. Compare with 01 Knapsack §4 where the inner loop runs descending to enforce single-use semantics — these are the only two iteration directions, and choosing the right one is non-negotiable.

4.4 Witness Reconstruction

To recover which items and how many of each compose the optimum, store a choice[i][w] array recording whether the take or skip branch won, then backtrack. In the 1D form, store a flat last_item[w] array recording which item was last added at capacity w; trace from w = W while subtracting weights[last_item[w]] until w = 0.

5. Complexity

Time: O(n · W). Derivation via the DP State Identification formula: n × (W + 1) states, each evaluated in O(1) work (a single max over two terms).
Space: O(n · W) in the 2D form, O(W) in the 1D rolling form.
Pseudo-polynomial caveat. Same as 01 Knapsack: nW is polynomial in the value of W, not in its bit length. For W = 10^9 the table has a billion cells — infeasible in either time or memory. The decision form of knapsack is NP-complete, and because that hardness depends on the magnitude of the numbers (encoded in binary), it is weakly NP-complete rather than strongly NP-complete (per the Wikipedia Knapsack article, citing Garey & Johnson 1979). For very large W, a fully polynomial-time approximation scheme (FPTAS) exists: an algorithm that, for any ε > 0, returns a value at least (1 − ε) times the optimum, in time polynomial in both n and 1/ε. For the unbounded problem specifically, Lawler’s 1979 scheme runs in O(n + 1/ε³) time with O(n + 1/ε²) space, and was improved by Jansen & Kraft (2015) to O(n + (1/ε²)·log³(1/ε)) time — note these bounds depend only on n and 1/ε, not on W, which is precisely what makes them practical when W is astronomically large. (The classic Lawler 1979 0/1-knapsack scheme, by contrast, is usually quoted as O(n·log(1/ε) + 1/ε⁴); the UKP-specific bounds above are the relevant ones here.)

6. UKP vs 0/1 Knapsack — The Comparison Table

Aspect	0/1 Knapsack	Unbounded Knapsack
Repetition allowed?	No (each item once)	Yes (any number of copies)
2D `take` branch reads	`dp[i-1][w - w_i] + v_i`	`dp[i ][w - w_i] + v_i`
1D inner-loop direction	Descending (`w = W..w_i`)	Ascending (`w = w_i..W`)
Reason for direction	Prevent re-use within one row	Allow re-use within one row
Time	`O(nW)`	`O(nW)`
Space (1D)	`O(W)`	`O(W)`
Greedy by density correct?	No (counterexamples easy to construct)	No — e.g. `w=[5,4], v=[10,7], W=8`: greedy 10, optimum 14 (§10.4)
Fractional version	Polynomial — sort by `v/w`, take greedily	Polynomial — also greedy by density
Canonical sub-problems	Subset Sum, Partition (LC 416)	Coin Change, Rod Cutting
LeetCode problems	416, 474, 494, 879	322, 518, 377, 343

The two are mirror images of each other in iteration order; everything else is structural similarity. Internalizing this table makes the family of “knapsack-shaped” problems reduce to two memorized loop directions.

7. Equivalence to Coin Change and Rod Cutting

7.1 Coin Change Variant A as UKP

Set weights[i] = coins[i] and values[i] = 1 for every coin, change max to min, change the base from dp[0] = 0 to dp[0] = 0 (still), require equality not inequality (so unreached cells stay at +∞), and you have minimum-coin change. The 1D ascending iteration is exactly the same. See Coin Change §4.1.

7.2 Coin Change Variant B as UKP-Counting

Replace max with += (accumulate), set dp[0] = 1, swap the loop nesting so coins are outermost, and you get number of combinations. The reason for the loop swap is to enforce a canonical generation order (avoid counting 1+2 and 2+1 as distinct) — this is unique to the counting variant and does not arise in value-maximizing UKP. See Coin Change §4.2 and §11.2.

7.3 Rod Cutting (CLRS Ch. 15.1)

weights[i] = i (a piece of length i), values[i] = price[i], capacity W = rod length n. Maximize total revenue. The recurrence simplifies because every “weight” is unique and equal to its index: dp[w] = max over i in 1..w of (price[i] + dp[w - i]). This is just UKP with the items implicitly defined by the price table. The canonical CLRS exposition uses this framing; recognizing it as UKP unifies the algorithmic content.

8. Bounded Knapsack — A Brief Cousin

The Bounded Knapsack Problem (BKP) sits between 0/1 and unbounded: each item i is available in at most k_i copies. Naive approach: replicate item i into k_i separate copies and run 0/1 KP — O(W · Σ k_i), possibly slow. Better: binary decomposition decomposes k_i = 1 + 2 + 4 + ... + 2^{j-1} + r and treats each chunk as a single 0/1 item with weight/value scaled accordingly, achieving O(nW log K_max). There is also an O(nW) monotonic-deque optimization (Pisinger 1995) for the per-item rolling-window subproblem. BKP is genuinely a separate algorithm; we mention it here for completeness but it is rarely asked in interviews.

9. Diagram — Same-Row vs Previous-Row Read

flowchart LR
    subgraph KP01[0/1 Knapsack]
        K1[dp i-1 w-wi<br/>previous row<br/>item already consumed] --> K2[dp i w<br/>current cell]
        K3[dp i-1 w<br/>skip] --> K2
    end
    subgraph UKP[Unbounded Knapsack]
        U1[dp i w-wi<br/>SAME row<br/>item still available] --> U2[dp i w<br/>current cell]
        U3[dp i-1 w<br/>skip entirely] --> U2
    end

What this diagram shows. The single arrow that distinguishes 0/1 knapsack from unbounded knapsack: in 0/1 the take branch reads dp[i-1][w-wi] (previous row — item is gone after taking it once), while in UKP the take branch reads dp[i][w-wi] (same row — item is still in the catalogue). In the 1D rolling-array form this corresponds to whether dp[w - wi] has already been updated in the current item’s pass: descending (0/1) leaves it as the previous item’s value; ascending (UKP) updates it first so it reflects “item used once already.” The skip branch is identical in both. Memorize this diagram and the iteration-order rules become trivial to derive from first principles.

10. Pitfalls

10.1 Wrong Iteration Direction in 1D (THE Canonical UKP Bug)

By far the most common mistake: copying the 01 Knapsack 1D template (which iterates w descending) and forgetting to flip it to ascending for UKP. Symptom: the algorithm runs and produces an answer that is silently identical to 0/1 knapsack’s answer (because the descending iteration prevents re-use). On a problem like rod-cutting where the optimum requires multiple copies of the same length, this returns a strict under-estimate. Fix: always re-derive which direction to use by remembering the recurrence — take reads same row → ascending; take reads previous row → descending.

10.2 Same-Row vs Previous-Row Confusion in 2D

In the 2D form, dp[i][w] = max(dp[i-1][w], dp[i][w - w_i] + v_i). Writing dp[i-1][w - w_i] in the take branch silently reduces UKP to 0/1 KP. The two characters i vs i-1 are the entire algorithmic difference. Always pause and check this when transcribing.

10.3 Forgetting to Multiply by the Correct Item Count in Reconstruction

If reconstructing the witness, “take” might happen many times for the same item. Naive backtracking that decrements i after each take (mimicking 0/1 reconstruction) misses the multi-take pattern. Either backtrack within the same i while dp[i][w] != dp[i-1][w], or store explicit count predecessors.

10.4 Mistaking UKP for Greedy

Like 0/1, UKP does not admit a value-density greedy. The cleanest counterexample: weights [5, 4], values [10, 7], capacity 8. Densities are v/w = 10/5 = 2.0 for item 1 and 7/4 = 1.75 for item 2, so a density-greedy takes item 1 first. After taking one copy of item 1 (weight 5, value 10), the remaining capacity is 8 − 5 = 3, into which neither item fits (item 1 needs 5, item 2 needs 4). Greedy therefore returns value 10. The true optimum is two copies of item 2: weight 4 + 4 = 8 ≤ 8, value 7 + 7 = 14 > 10. The densest item “wins per gram” but wastes 3 units of capacity it cannot fill; the slightly-less-dense item tiles the capacity exactly. This is exactly the structural reason greedy fails — density ignores the packing remainder.

What George Dantzig’s greedy does guarantee for UKP is a 1/2-approximation: filling with as many copies of the densest item as fit yields at least half the optimal value (per the Wikipedia Knapsack article). The fractional relaxation, where fractional copies are allowed, is solved exactly by the density greedy — you simply pour the densest item until the knapsack is full. The integrality gap between the fractional optimum and the integer optimum is what the DP exists to close. Default to DP for the exact integer answer.

10.5 Treating `weights[i] = 0` Without Guarding

If a problem permits zero-weight items with positive value, the 1D recurrence loops infinitely (dp[w] = dp[w - 0] + v keeps incrementing). Sanitize input: zero-weight positive-value items should be taken infinitely, which usually means the answer is +∞ and the problem is ill-posed; reject or special-case.

10.6 Off-by-One in 1D Inner Loop Bounds

for w in range(w_i, W + 1) is correct; for w in range(w_i, W) misses the final cell. range(0, W + 1) with an if w >= w_i guard is also correct but slightly less clean. Always test the boundary w = W explicitly.

10.7 Forgetting the `dp[0] = 0` Initialization

Initializing the table to all zeros handles the base case automatically for the value-maximizing UKP. But for the minimum-coins variant (Coin Change A), the base is dp[0] = 0 while all other entries start at +∞. Using zeros there causes every cell to read 0 + 1 = 1 and the algorithm returns 1 for everything. Always re-derive base cases from the problem semantics.

10.8 Confusing UKP with the Counting Variant’s Loop Order

The value-maximizing UKP can iterate the loops in either order (items outer + capacity inner, or capacity outer + items inner) because max is order-insensitive. The counting variant (number of combinations) requires items outer to avoid permutation double-counting — this is a separate constraint, not inherited from value-maximization. Don’t carry the constraint over when it doesn’t apply.

10.9 State Definition Drift

dp[i][w] here means “items 1..i available, capacity ≤ w.” A valid alternative is “items i..n available, capacity ≤ w” (right-extending). They produce the same answer but require different base cases and traversal directions. Pick one convention and write it down before coding; mid-stream switching introduces silent bugs.

10.10 Pseudo-Polynomial Memory Blowup

For W = 10^6 and n = 100, the 2D table has 10^8 cells — usually too large. The 1D rolling form O(W) = O(10^6) is fine. If W itself is large (> 10^7), even 1D is infeasible and you need either FPTAS or to recognize that the problem has a smaller equivalent state.

11. Diagram — Iteration Order Comparison

flowchart TB
    subgraph KP01Loop[0/1 Knapsack 1D inner loop: descending]
        A1[w = W] --> A2[w = W-1] --> A3[...] --> A4[w = w_i]
        A4 --> A5[reads dp w-wi from PREVIOUS item's row]
    end
    subgraph UKPLoop[Unbounded Knapsack 1D inner loop: ascending]
        B1[w = w_i] --> B2[w = w_i + 1] --> B3[...] --> B4[w = W]
        B4 --> B5[reads dp w-wi from CURRENT item's row]
    end

What this diagram shows. The 1D inner-loop direction for the two knapsack variants and what the relevant read returns under each direction. In 0/1 (top), iterating w from W down to w_i ensures that when we update dp[w], the cell dp[w - w_i] we read still holds its value from the previous item’s iteration — preventing a single item from being taken twice. In UKP (bottom), iterating w from w_i up to W ensures that dp[w - w_i] has already been updated under the current item — explicitly allowing additional copies to be picked up. Same code shape, opposite direction, opposite semantics. Memorize this picture.

12. Common Interview Problems

Problem	LeetCode #	Pattern
Coin Change	LC 322	UKP-min: minimize coins for exact target
Coin Change II	LC 518	UKP-count: combinations (loop order matters)
Combination Sum IV	LC 377	UKP-permutations (swapped loop order)
Perfect Squares	LC 279	UKP-min where coins = perfect squares
Integer Break	LC 343	Maximize product of integer parts summing to n
Rod Cutting	CLRS 15.1	Classic UKP, length = weight
Word Break	LC 139	Boolean UKP over string prefixes (dictionary as items)
Concatenated Words	LC 472	Multi-pass Word Break
Minimum Cost For Tickets	LC 983	UKP-flavored with date-budget structure

13. Open Questions

Are there strictly polynomial algorithms for UKP under additional structural assumptions (e.g., few distinct denominations, bounded value-to-weight ratio)? The “few items, large weights” case admits ILP-based methods (Eisenbrand & Weismantel 2018).
How does UKP behave under online / streaming constraints — items arriving over time, must commit to “take how many” as they appear?
(Resolved — see §10.4.) A clean integer counterexample is w=[5,4], v=[10,7], W=8: greedy yields 10, the optimum is 14. Dantzig’s greedy is a 1/2-approximation in general.
When the capacity W is enormous (10^18) but n and item weights are small, can we exploit periodicity / number-theoretic structure to short-circuit the DP? (Yes — for W larger than some threshold, the optimum becomes “as many of the densest item as fit, plus a small remainder solved by tiny DP.” Quantifying the threshold is a known result; verify against Kellerer et al. 2004.)

14. See Also

01 Knapsack — the bounded sibling; iteration-direction contrast
Coin Change — direct application of UKP machinery (min and count variants)
Partition Equal Subset Sum — 0/1 KP feasibility variant; contrast with UKP-feasibility
Memoization vs Tabulation — foundational DP framework
DP State Identification — recognition recipe; UKP is a canonical “budget DP”
Greedy Algorithms — for the fractional-knapsack greedy that does work
Big-O Notation — pseudo-polynomial complexity discussion
SWE Interview Preparation MOC

vault

Explorer

Unbounded Knapsack

Unbounded Knapsack

1. Intuition — The All-You-Can-Pack Buffet

2. Tiny Worked Example

3. Pseudocode

4. Python Implementation

4.1 Top-Down (Memoization)

4.2 Bottom-Up Tabulation — 2D

4.3 Bottom-Up Tabulation — 1D Rolling Array

4.4 Witness Reconstruction

5. Complexity

6. UKP vs 0/1 Knapsack — The Comparison Table

7. Equivalence to Coin Change and Rod Cutting

7.1 Coin Change Variant A as UKP

7.2 Coin Change Variant B as UKP-Counting

7.3 Rod Cutting (CLRS Ch. 15.1)

8. Bounded Knapsack — A Brief Cousin

9. Diagram — Same-Row vs Previous-Row Read

10. Pitfalls

10.1 Wrong Iteration Direction in 1D (THE Canonical UKP Bug)

10.2 Same-Row vs Previous-Row Confusion in 2D

10.3 Forgetting to Multiply by the Correct Item Count in Reconstruction

10.4 Mistaking UKP for Greedy

10.5 Treating `weights[i] = 0` Without Guarding

10.6 Off-by-One in 1D Inner Loop Bounds

10.7 Forgetting the `dp[0] = 0` Initialization

10.8 Confusing UKP with the Counting Variant’s Loop Order

10.9 State Definition Drift

10.10 Pseudo-Polynomial Memory Blowup

11. Diagram — Iteration Order Comparison

12. Common Interview Problems

13. Open Questions

14. See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Unbounded Knapsack

Unbounded Knapsack

1. Intuition — The All-You-Can-Pack Buffet

2. Tiny Worked Example

3. Pseudocode

4. Python Implementation

4.1 Top-Down (Memoization)

4.2 Bottom-Up Tabulation — 2D

4.3 Bottom-Up Tabulation — 1D Rolling Array

4.4 Witness Reconstruction

5. Complexity

6. UKP vs 0/1 Knapsack — The Comparison Table

7. Equivalence to Coin Change and Rod Cutting

7.1 Coin Change Variant A as UKP

7.2 Coin Change Variant B as UKP-Counting

7.3 Rod Cutting (CLRS Ch. 15.1)

8. Bounded Knapsack — A Brief Cousin

9. Diagram — Same-Row vs Previous-Row Read

10. Pitfalls

10.1 Wrong Iteration Direction in 1D (THE Canonical UKP Bug)

10.2 Same-Row vs Previous-Row Confusion in 2D

10.3 Forgetting to Multiply by the Correct Item Count in Reconstruction

10.4 Mistaking UKP for Greedy

10.5 Treating weights[i] = 0 Without Guarding

10.6 Off-by-One in 1D Inner Loop Bounds

10.7 Forgetting the dp[0] = 0 Initialization

10.8 Confusing UKP with the Counting Variant’s Loop Order

10.9 State Definition Drift

10.10 Pseudo-Polynomial Memory Blowup

11. Diagram — Iteration Order Comparison

12. Common Interview Problems

13. Open Questions

14. See Also

Graph View

Table of Contents

Backlinks

10.5 Treating `weights[i] = 0` Without Guarding

10.7 Forgetting the `dp[0] = 0` Initialization