Loading…

mediumDynamic ProgrammingFrequently asked

Unbounded Knapsack

Q: How do you solve Unbounded Knapsack using the Brute Force — Recursion Over Remaining Capacity approach?

When to use it: Say this first to establish the reusable-item recurrence, then flag the exponential branching before optimizing. Reason about one placement at a time. To best fill capacity `rem`, try every item `i` that fits, collect `value[i]`, and recursively best-fill the remaining capacity `rem - weight[i]`. Take the maximum over all those choices. The base case is `best(0) = 0`, and if no item fits the result is `0` (pack nothing more). **The mental shift: place one item, recurse on the same menu.** Don't plan the whole multiset up front. Commit to a single item, reduce the capacity, and solve the identical problem on what remains. The key difference from 0/1: because items repeat, the recursive call faces the *same* full set of items — we do **not** advance an item index or remove anything. That reusability is the entire definition of 'unbounded'. **Why max of value.** We're choosing the most valuable way to use the remaining room, so we combine the per-item options with `max`. Each option is an alternative, not a companion, so we never sum across items. **Why the fit guard.** Trying an item heavier than `rem` would index a negative capacity; we only consider items with `weight[i] <= rem`. **Why we don't ship this.** The same `rem` is recomputed through countless item orderings — exponential overlap on a single state variable. Cache `best(rem)` and the blowup disappears. Time complexity: O(nᵂ). Space complexity: O(W).

Q: How do you solve Unbounded Knapsack using the Top-Down Memoization on Remaining Capacity approach?

When to use it: The fix once you name the overlap — 'cache the best value for each remaining capacity'. Keep the place-one-item recurrence but cache `best(rem)` so each remaining capacity is solved exactly once. A `memo` array indexed by remaining capacity starts 'uncomputed'; we return the cached value on entry and store the result before returning. **The mental shift: the answer depends only on the remaining capacity.** Any two paths that arrive at the same `rem` have identical futures, because the item menu never changes (items are unlimited). So the only thing distinguishing a state is how much room is left — caching by `rem` collapses all duplicate explorations into one. The state space is the integers `0..W`, which is why the complexity becomes linear-ish in `W`. **Why a 1-D memo suffices — unlike 0/1.** In 0/1 knapsack the answer depended on *both* the item index and the capacity (which items remain matters). Here the items never get consumed, so the item index is irrelevant — `rem` alone is the complete state, and a single-dimensional cache is enough. **Why -1 as sentinel.** 0 is a legitimate best value (nothing fits), so it can't double as 'uncomputed'; initialize the memo to -1. **A language note.** This top-down version recurses up to `W` deep (with a weight-1 item). For `W = 10⁴` Java handles it, but Python's default recursion limit is about 1000 — deep recursion will raise `RecursionError`. That's the practical reason the bottom-up table (next) is the default in Python. Time complexity: O(nW). Space complexity: O(W).

Q: How do you solve Unbounded Knapsack using the Bottom-Up — 1-D dp[] Table, Capacity ASCENDING (Optimal) approach?

When to use it: The answer they want. Frame it as 'fill dp[0..W] ascending; reuse is what the ascending sweep gives you for free'. Build the answers bottom-up. `dp[w]` is the maximum value that fits in capacity `w`. Anchor `dp[0] = 0`, then for each capacity `w` from `1` to `W`, try every item that fits and relax `dp[w] = max(dp[w], value[i] + dp[w - weight[i]])`. The answer is `dp[W]`. **The mental shift: solve every smaller capacity first.** Because `dp[w]` only looks *down* to `dp[w - weight]` for positive weights, processing capacities in increasing order guarantees every dependency is final when you reach it. No recursion, no stack — one clean sweep. **Why ASCENDING is the whole trick.** This is the mirror image of 0/1 knapsack. When we relax `dp[w]` using `dp[w - weight[i]]`, that smaller cell has *already been updated in this same pass* and may itself include item `i`. So adding item `i` again on top of it means we've used item `i` multiple times — exactly the reuse we want. In 0/1 we iterated descending precisely to *prevent* this; here we iterate ascending to *enable* it. One loop direction, two completely different problems. **Why one shared array works without an item dimension.** Since items are reusable, the item index is not part of the state — only the capacity is. A single `dp[w]` over capacities, swept ascending while looping items inside, captures every multiset. (Looping capacities outer and items inner, or items outer and capacities inner, both work for the max-value version because order of items doesn't matter here.) **Why dp[0] = 0 anchors everything.** Every reachable capacity's value is built from `dp[0]` through a chain of item additions. Leave `dp[0]` unset and no capacity could be relaxed. Time complexity: O(nW). Space complexity: O(W).

Dynamic Programming · 25 of 44 · 10 min

You are given n item types, where type i has a positive weight[i] and a positive value[i], and a knapsack of maximum weight capacity W.

Maximize the total value of items placed in the knapsack without exceeding W. Unlike 0/1 knapsack, you may use each item type an **unlimited number of times** (any non-negative count of each).

Return the maximum total value achievable.

In plain English

Fill a knapsack of capacity W to maximize value, where each item type is an inexhaustible supply. The only change from 0/1 knapsack is repetition: after taking an item you may take it again. That single difference flips the space-optimized loop direction and lets the take branch stay on the same item.

Examples

Example 1

Input: weight = [1, 3, 4, 5], value = [10, 40, 50, 70], W = 8
Output: 110
Note: Two copies of the weight-4 item (value 50 each) fill capacity 8 for value 100... but weight 3 + weight 5 gives 40 + 70 = 110, the best. Reuse is allowed but not required here.

Example 2

Input: weight = [2, 3], value = [5, 8], W = 6
Output: 16
Note: Two copies of the weight-3 item (8 + 8 = 16) beat three copies of weight-2 (5×3 = 15).

Example 3

Input: weight = [3], value = [4], W = 10
Output: 12
Note: Pack three copies of the weight-3 item (3×3 = 9 ≤ 10) for value 12; a fourth wouldn't fit.

Constraints

1 ≤ n ≤ 100
1 ≤ weight[i], value[i] ≤ 1000
1 ≤ W ≤ 10⁴
All weights and values are integers

Clarifying questions5First question: Can I use an item type more than once?Explore questions

Q1.Can I use an item type more than once?
Yes — unlimited copies of each. That's what makes it 'unbounded'. If each were single-use it would be 0/1 knapsack.
Q2.Is there a limit on how many of one item I can pack?
Only the capacity limits it — you can pack floor(W / weight[i]) copies of item i if that's optimal.
Q3.Can I take a fraction of an item?
No, whole items only. Fractions would make it the greedy fractional knapsack problem instead.
Q4.What if no item fits in W?
The answer is 0 — the empty selection is always valid. The dp array initialized to 0 handles this.
Q5.Does the order I pack items in matter?
No — only the multiset of chosen items affects the value. The DP naturally ignores order.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Maximize total value within capacity W, but each item may be used any number of times. The recurrence is dp[w] = max over items i of value[i] + dp[w - weight[i]] — taking item i still leaves item i available. Naive recursion is exponential; memoize on remaining capacity or build a 1-D dp[] table iterating weight ASCENDING (so an item can be re-used within the same pass). O(nW).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can distinguish reusable-item optimization from the 0/1 case and articulate why the single 1-D loop direction flips from descending to ascending.

Where candidates slip

Iterating capacity descending out of 0/1 habit (which forbids reuse and undercounts), or shrinking the item set in the take branch as if items were single-use.

How to stand out

Derive the recurrence, then say explicitly: 'this is 0/1 knapsack but the items repeat, so I sweep capacity ascending — dp[w - weight] should already include this item.' Connect it to Coin Change and Rod Cutting.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Over Remaining Capacity	`O(nᵂ)`	`O(W)`	Say this first to establish the reusable-item recurrence, then flag the exponential branching before optimizing.	Read
2	Top-Down Memoization on Remaining Capacity	`O(nW)`	`O(W)`	The fix once you name the overlap — 'cache the best value for each remaining capacity'.	Read
3	Bottom-Up — 1-D dp[] Table, Capacity ASCENDING (Optimal)Optimal	`O(nW)`	`O(W)`	The answer they want. Frame it as 'fill dp[0..W] ascending; reuse is what the ascending sweep gives you for free'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMaximize value under capacity WEach item once or unlimited?Once eachUnlimitedExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Over Remaining Capacity

TimeO(nᵂ)SpaceO(W)

Say this first to establish the reusable-item recurrence, then flag the exponential branching before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Think about the NEXT item you place into the remaining capacity. After placing it, what's left to solve?

2Hint 2Explore hint

If you place item i (only when weight[i] ≤ rem), you gain value[i] and still face the SAME item menu with capacity rem - weight[i] — because items are reusable.

3Hint 3Explore hint

best(rem) = max over items i of value[i] + best(rem - weight[i]), with best(0) = 0 and no item fitting → 0.

A · Core idea

Reason about one placement at a time. To best fill capacity rem, try every item i that fits, collect value[i], and recursively best-fill the remaining capacity rem - weight[i]. Take the maximum over all those choices. The base case is best(0) = 0, and if no item fits the result is 0 (pack nothing more).

The mental shift: place one item, recurse on the same menu. Don't plan the whole multiset up front. Commit to a single item, reduce the capacity, and solve the identical problem on what remains. The key difference from 0/1: because items repeat, the recursive call faces the same full set of items — we do not advance an item index or remove anything. That reusability is the entire definition of 'unbounded'.

Why max of value. We're choosing the most valuable way to use the remaining room, so we combine the per-item options with max. Each option is an alternative, not a companion, so we never sum across items.

Why the fit guard. Trying an item heavier than rem would index a negative capacity; we only consider items with weight[i] <= rem.

Why we don't ship this. The same rem is recomputed through countless item orderings — exponential overlap on a single state variable. Cache best(rem) and the blowup disappears.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

weight = [2, 3], value = [5, 8], W = 6

best(6)

item wt2 → 5 + best(4); item wt3 → 8 + best(3)

Statebranches out

Final result16

C · Code with teaching comments

Reference implementation previewpublic int unboundedKnapsack(int[] weight, int[] value, int W) { return best(weight, value, W); } private int best(int[] weight, int[] value, int rem) {Explore the full code

solution.javaJava

Brute Force — Recursion Over Remaining Capacity — reference

3 teaching notes

1
public int unboundedKnapsack(int[] weight, int[] value, int W) {
2
    return best(weight, value, W);
3
}
4
 
5
private int best(int[] weight, int[] value, int rem) {
6
    // Base case: no capacity left means no more value can be added — return 0.
7
    if (rem == 0) {
8
        return 0;
9
    }
10
    int top = 0;
11
    for (int i = 0; i < weight.length; i++) {
12
        // Only try items that still fit, so rem - weight[i] never goes negative.
13
        if (weight[i] <= rem) {
14
            // Take item i and recurse on the SAME menu — that reuse is what makes it
15
            // unbounded.
16
            top = Math.max(top, value[i] + best(weight, value, rem - weight[i]));
17
        }
18
    }
19
    return top;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(nᵂ) timeO(W) spaceOpen the invariant and proofExplore the proof

The recurrence depends on exactly one number — the remaining capacity — yet the naive tree resolves best(rem) repeatedly via different item orders. One state variable plus heavy overlap is the canonical signal for an O(W·n) DP.

ComplexityO(nᵂ) time, O(W) space — Each call branches into up to n recursive calls and recursion can descend ~W levels (using a weight-1 item), giving exponential nᵂ nodes in the worst case. Stack depth is O(W).

E · Edge cases and pitfalls4W = 0 — best(0) returns 0 immediately — nothing can be packed.Explore edge cases

Edge cases handled

W = 0best(0) returns 0 immediately — nothing can be packed.

Pitfalls

Advancing an item index in the recursion — that turns it into 0/1 and forbids reuse.
Forgetting the weight[i] <= rem guard — negative capacity subproblem.
Skipping this approach — interviewers want to hear the recurrence before the table.

03.2

Approach 2 of 3

Top-Down Memoization on Remaining Capacity

TimeO(nW)SpaceO(W)

The fix once you name the overlap — 'cache the best value for each remaining capacity'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

best(rem) returns the same answer every time. Where can you store it so each capacity is solved once?

2Hint 2Explore hint

Add a memo of size W+1 indexed by remaining capacity. Check on entry, fill before returning.

3Hint 3Explore hint

memo[rem] = max over fitting items of value[i] + best(rem - weight[i]); use -1 for 'uncomputed' since 0 is valid.

A · Core idea

Keep the place-one-item recurrence but cache best(rem) so each remaining capacity is solved exactly once. A memo array indexed by remaining capacity starts 'uncomputed'; we return the cached value on entry and store the result before returning.

The mental shift: the answer depends only on the remaining capacity. Any two paths that arrive at the same rem have identical futures, because the item menu never changes (items are unlimited). So the only thing distinguishing a state is how much room is left — caching by rem collapses all duplicate explorations into one. The state space is the integers 0..W, which is why the complexity becomes linear-ish in W.

Why a 1-D memo suffices — unlike 0/1. In 0/1 knapsack the answer depended on both the item index and the capacity (which items remain matters). Here the items never get consumed, so the item index is irrelevant — rem alone is the complete state, and a single-dimensional cache is enough.

Why -1 as sentinel. 0 is a legitimate best value (nothing fits), so it can't double as 'uncomputed'; initialize the memo to -1.

A language note. This top-down version recurses up to W deep (with a weight-1 item). For W = 10⁴ Java handles it, but Python's default recursion limit is about 1000 — deep recursion will raise RecursionError. That's the practical reason the bottom-up table (next) is the default in Python.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

weight = [1, 3, 4, 5], value = [10, 40, 50, 70], W = 8

best(8)

needs best(7), best(5), best(4), best(3)

Statememo empty

Final result110

C · Code with teaching comments

Reference implementation previewpublic int unboundedKnapsack(int[] weight, int[] value, int W) { int[] memo = new int[W + 1]; Arrays.fill(memo, -1); return best(weight, value, W, memo); }Explore the full code

solution.javaJava

Top-Down Memoization on Remaining Capacity — reference

4 teaching notes

1
public int unboundedKnapsack(int[] weight, int[] value, int W) {
2
    int[] memo = new int[W + 1];
3
    // -1 means 'uncomputed' — distinct from the valid best value 0.
4
    Arrays.fill(memo, -1);
5
    return best(weight, value, W, memo);
6
}
7
 
8
private int best(int[] weight, int[] value, int rem, int[] memo) {
9
    if (rem == 0) {
10
        return 0;
11
    }
12
    // Cache hit — return the stored best for this remaining capacity in O(1).
13
    if (memo[rem] != -1) {
14
        return memo[rem];
15
    }
16
    int top = 0;
17
    for (int i = 0; i < weight.length; i++) {
18
        if (weight[i] <= rem) {
19
            // Try every item; the recursion stays on the full menu, allowing reuse.
20
            top = Math.max(top, value[i] + best(weight, value, rem - weight[i], memo));
21
        }
22
    }
23
    // Store the resolved best before returning so this capacity is never recomputed.
24
    memo[rem] = top;
25
    return top;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(nW) timeO(W) spaceOpen the invariant and proofExplore the proof

Same mechanical DP upgrade as Coin Change: a correct recurrence plus a cache keyed on the only state that matters. The hard part is recognizing that 'remaining capacity' fully determines the future precisely because items are reusable — drop reusability and you'd need the item dimension back.

ComplexityO(nW) time, O(W) space — There are W+1 distinct remaining-capacity states. Each does O(n) work scanning items → O(nW) time. The memo plus recursion stack is O(W).

E · Edge cases and pitfalls5W = 0 — best(0) = 0 immediately.Explore edge cases

Edge cases handled

W = 0best(0) = 0 immediately.
no item fits WLoop adds nothing; memo[W] = 0 → answer 0.

Pitfalls

Using 0 as 'uncomputed' — collides with the valid answer 0; use -1.
Indexing the memo at W instead of W+1 entries — capacities 0..W need W+1 slots.
Deep recursion in Python (rem up to W) can blow the ~1000 recursion limit — prefer tabulation for large W.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — 1-D dp[] Table, Capacity ASCENDING (Optimal)

TimeO(nW)SpaceO(W)

The answer they want. Frame it as 'fill dp[0..W] ascending; reuse is what the ascending sweep gives you for free'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Compute the best value for capacity 1, then 2, ... up to W, reusing earlier answers.

2Hint 2Explore hint

dp[w] = best value within capacity w. dp[0] = 0; for each w try every fitting item: dp[w] = max(dp[w], value[i] + dp[w - weight[i]]).

3Hint 3Explore hint

Sweep w ASCENDING. Because dp[w - weight] is already finalized AND may itself include item i, the same item gets reused automatically — the opposite of 0/1's descending sweep.

A · Core idea

Build the answers bottom-up. dp[w] is the maximum value that fits in capacity w. Anchor dp[0] = 0, then for each capacity w from 1 to W, try every item that fits and relax dp[w] = max(dp[w], value[i] + dp[w - weight[i]]). The answer is dp[W].

The mental shift: solve every smaller capacity first. Because dp[w] only looks down to dp[w - weight] for positive weights, processing capacities in increasing order guarantees every dependency is final when you reach it. No recursion, no stack — one clean sweep.

Why ASCENDING is the whole trick. This is the mirror image of 0/1 knapsack. When we relax dp[w] using dp[w - weight[i]], that smaller cell has already been updated in this same pass and may itself include item i. So adding item i again on top of it means we've used item i multiple times — exactly the reuse we want. In 0/1 we iterated descending precisely to prevent this; here we iterate ascending to enable it. One loop direction, two completely different problems.

Why one shared array works without an item dimension. Since items are reusable, the item index is not part of the state — only the capacity is. A single dp[w] over capacities, swept ascending while looping items inside, captures every multiset. (Looping capacities outer and items inner, or items outer and capacities inner, both work for the max-value version because order of items doesn't matter here.)

Why dp[0] = 0 anchors everything. Every reachable capacity's value is built from dp[0] through a chain of item additions. Leave dp[0] unset and no capacity could be relaxed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

weight = [2, 3], value = [5, 8], W = 6

Array state

init

dp[0]=0, rest 0

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result16

C · Code with teaching comments

solution.javaJava

Bottom-Up — 1-D dp[] Table, Capacity ASCENDING (Optimal) — optimal

4 teaching notes

1
public int unboundedKnapsack(int[] weight, int[] value, int W) {
2
    // dp[w] = best value within capacity w; defaults to 0, which is also the dp[0]
3
    // anchor.
4
    int[] dp = new int[W + 1];
5
    // ASCENDING capacities — dp[w - weight] is already final and may include this item,
6
    // enabling reuse.
7
    for (int w = 1; w <= W; w++) {
8
        for (int i = 0; i < weight.length; i++) {
9
            // Only relax with items that fit, so w - weight[i] is non-negative.
10
            if (weight[i] <= w) {
11
                // Take item i on top of the best fill of the remaining capacity. The
12
                // whole DP in one line.
13
                dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
14
            }
15
        }
16
    }
17
    return dp[W];
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(nW) timeO(W) spaceOpen the invariant and proofExplore the proof

Unbounded knapsack is the parent of Coin Change (min count) and Rod Cutting (max price): all three are 'reusable items, fill a target' DPs distinguished only by the objective. The ascending sweep is the signature — see it and you know reuse is allowed. Flip to descending and you've silently switched to 0/1.

ComplexityO(nW) time, O(W) space — The outer loop runs W times, the inner loop scans n items → O(nW) time. A single dp array of size W+1 → O(W) space, no recursion stack.

E · Edge cases and pitfalls6W = 0 — Outer loop never runs; dp[0] = 0 returned — empty knapsack.Explore edge cases

Edge cases handled

W = 0Outer loop never runs; dp[0] = 0 returned — empty knapsack.
single weight-1 itemdp[w] = w × value, packing W copies of the unit item.
no item fits WInner guard always fails; dp stays 0 → answer 0.

Pitfalls

Iterating capacity DESCENDING out of 0/1 habit — forbids reuse and undercounts the value.
Forgetting the weight[i] <= w guard — negative index into dp.
Confusing this with the COUNT-of-ways variant, where the item/capacity loop nesting changes the meaning.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int unboundedKnapsack(int[] weight, int[] value, int W) { int[] dp = new int[W + 1]; for (int w = 1; w <= W; w++) { for (int i = 0; i < weight.length; i++) { if (weight[i] <= w) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Descending sweep kills reuse

Descending order keeps dp[w - weight] at its pre-item value, which is exactly 0/1 behavior. For unbounded you WANT dp[w - weight] to already include the item, so you must sweep ascending.

Explore the code comparison

Don't write this

for (int w = W; w >= 1; w--) {          // DESCENDING — 0/1 behavior
    for (int i = 0; i < weight.length; i++)
        if (weight[i] <= w)
            dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
}

Write this instead

for (int w = 1; w <= W; w++) {          // ASCENDING — allows reuse
    for (int i = 0; i < weight.length; i++)
        if (weight[i] <= w)
            dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
}

Advancing the item index in recursion

Recursing on i+1 (or shrinking the item list) forbids reusing an item — that's the 0/1 recurrence. Unbounded must recurse on the SAME item set.

Explore the code comparison

Don't write this

def best(i, rem):
    if i == len(weight) or rem == 0:
        return 0
    take = value[i] + best(i + 1, rem - weight[i])  # advances i — single use
    return max(best(i + 1, rem), take)

Write this instead

def best(rem):
    top = 0
    for i in range(len(weight)):
        if weight[i] <= rem:
            top = max(top, value[i] + best(rem - weight[i]))  # same menu
    return top

Sentinel collides with a valid 0

0 is a legitimate best value (nothing fits), so it can't also mean 'uncomputed'. Initialize the memo to -1.

Explore the code comparison

Don't write this

int[] memo = new int[W + 1]; // all 0
if (memo[rem] != 0) return memo[rem];

Write this instead

int[] memo = new int[W + 1];
Arrays.fill(memo, -1);
if (memo[rem] != -1) return memo[rem];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Unbounded knapsack — reusable items, 1-D table swept ASCENDING

Code pattern to memorize

dp[0] = 0
for w in 1..W:
    for each item i with weight[i] <= w:
        dp[w] = max(dp[w], value[i] + dp[w - weight[i]])
return dp[W]

Rules to remember

1Each item is reusable unlimited times — the take branch recurses on the same item set, never shrinking it.
2Iterate capacity ASCENDING (1 → W). That's the exact opposite of 0/1, and it's what lets dp[w - weight] already include the item you're adding again.
3It's a max of value: dp[w] = max(dp[w], value[i] + dp[w - weight[i]]).
4Anchor dp[0] = 0 — zero capacity yields zero value — and start every other cell at 0 (taking nothing is always allowed).
5Only relax dp[w] from a fitting item (weight[i] <= w) to avoid a negative index.

Use this pattern when

Maximize value/score under one capacity with items reusable any number of times
Choosing how many of each denomination/piece to use, repetition allowed
Order of selection doesn't matter, only the multiset of chosen items
Coin Change / Rod Cutting flavored problems (reuse permitted)

Choose another pattern when

Each item usable at most once → 0/1 knapsack, iterate capacity DESCENDING
You want the COUNT of ways to fill, not the max value → counting DP (loop order matters)
Capacity is astronomically large → O(nW) table infeasible, rethink with math/BFS
Fractions allowed → greedy fractional knapsack by ratio, no DP needed

Interview takeaway

Unbounded knapsack is 0/1's twin with one line changed: sweep capacity ascending instead of descending. Ascending lets dp[w - weight] already contain the item you're re-adding, encoding 'use it again'. Coin Change (min count) and Rod Cutting (max price) are unbounded knapsack in disguise — once you see the ascending sweep, you recognize the whole family.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical unbounded knapsack — reusable-item value maximization. Recognize it whenever you fill one capacity to optimize value with each item type available unlimited times. Identical skeleton to Coin Change (min count) and Rod Cutting (max price); the ascending capacity sweep is what distinguishes it from 0/1 knapsack.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Coin Change
Unbounded knapsack minimizing the COUNT of items to hit an exact target — swap max-value for min-count.
Coin Change II
Coming soon
Count the NUMBER OF ways to fill the target with reusable coins — loop coins outer to avoid counting permutations.
Rod Cutting
Maximize price by cutting a rod — unbounded knapsack where a length-i piece is a reusable 'item' of weight i and value price[i].
Combination Sum IV
Coming soon
Count ordered sequences (permutations) summing to target — capacity outer, items inner.

Same pattern

←

Subset Sum

Continue · Next problem

0/1 Knapsack

mediumDynamic ProgrammingFrequently asked

Unbounded Knapsack

Dynamic Programming · 25 of 44 · 10 min

You are given n item types, where type i has a positive weight[i] and a positive value[i], and a knapsack of maximum weight capacity W.

Maximize the total value of items placed in the knapsack without exceeding W. Unlike 0/1 knapsack, you may use each item type an **unlimited number of times** (any non-negative count of each).

Return the maximum total value achievable.

In plain English

Examples

Example 1

Input: weight = [1, 3, 4, 5], value = [10, 40, 50, 70], W = 8
Output: 110
Note: Two copies of the weight-4 item (value 50 each) fill capacity 8 for value 100... but weight 3 + weight 5 gives 40 + 70 = 110, the best. Reuse is allowed but not required here.

Example 2

Input: weight = [2, 3], value = [5, 8], W = 6
Output: 16
Note: Two copies of the weight-3 item (8 + 8 = 16) beat three copies of weight-2 (5×3 = 15).

Example 3

Input: weight = [3], value = [4], W = 10
Output: 12
Note: Pack three copies of the weight-3 item (3×3 = 9 ≤ 10) for value 12; a fourth wouldn't fit.

Constraints

1 ≤ n ≤ 100
1 ≤ weight[i], value[i] ≤ 1000
1 ≤ W ≤ 10⁴
All weights and values are integers

Clarifying questions5First question: Can I use an item type more than once?Explore questions

Q1.Can I use an item type more than once?
Yes — unlimited copies of each. That's what makes it 'unbounded'. If each were single-use it would be 0/1 knapsack.
Q2.Is there a limit on how many of one item I can pack?
Only the capacity limits it — you can pack floor(W / weight[i]) copies of item i if that's optimal.
Q3.Can I take a fraction of an item?
No, whole items only. Fractions would make it the greedy fractional knapsack problem instead.
Q4.What if no item fits in W?
The answer is 0 — the empty selection is always valid. The dp array initialized to 0 handles this.
Q5.Does the order I pack items in matter?
No — only the multiset of chosen items affects the value. The DP naturally ignores order.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can distinguish reusable-item optimization from the 0/1 case and articulate why the single 1-D loop direction flips from descending to ascending.

Where candidates slip

Iterating capacity descending out of 0/1 habit (which forbids reuse and undercounts), or shrinking the item set in the take branch as if items were single-use.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Over Remaining Capacity	`O(nᵂ)`	`O(W)`	Say this first to establish the reusable-item recurrence, then flag the exponential branching before optimizing.	Read
2	Top-Down Memoization on Remaining Capacity	`O(nW)`	`O(W)`	The fix once you name the overlap — 'cache the best value for each remaining capacity'.	Read
3	Bottom-Up — 1-D dp[] Table, Capacity ASCENDING (Optimal)Optimal	`O(nW)`	`O(W)`	The answer they want. Frame it as 'fill dp[0..W] ascending; reuse is what the ascending sweep gives you for free'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Over Remaining Capacity

TimeO(nᵂ)SpaceO(W)

Say this first to establish the reusable-item recurrence, then flag the exponential branching before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Think about the NEXT item you place into the remaining capacity. After placing it, what's left to solve?

2Hint 2Explore hint

If you place item i (only when weight[i] ≤ rem), you gain value[i] and still face the SAME item menu with capacity rem - weight[i] — because items are reusable.

3Hint 3Explore hint

best(rem) = max over items i of value[i] + best(rem - weight[i]), with best(0) = 0 and no item fitting → 0.

A · Core idea

Why the fit guard. Trying an item heavier than rem would index a negative capacity; we only consider items with weight[i] <= rem.

Why we don't ship this. The same rem is recomputed through countless item orderings — exponential overlap on a single state variable. Cache best(rem) and the blowup disappears.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

weight = [2, 3], value = [5, 8], W = 6

best(6)

item wt2 → 5 + best(4); item wt3 → 8 + best(3)

Statebranches out

Final result16

C · Code with teaching comments

solution.javaJava

Brute Force — Recursion Over Remaining Capacity — reference

3 teaching notes

1
public int unboundedKnapsack(int[] weight, int[] value, int W) {
2
    return best(weight, value, W);
3
}
4
 
5
private int best(int[] weight, int[] value, int rem) {
6
    // Base case: no capacity left means no more value can be added — return 0.
7
    if (rem == 0) {
8
        return 0;
9
    }
10
    int top = 0;
11
    for (int i = 0; i < weight.length; i++) {
12
        // Only try items that still fit, so rem - weight[i] never goes negative.
13
        if (weight[i] <= rem) {
14
            // Take item i and recurse on the SAME menu — that reuse is what makes it
15
            // unbounded.
16
            top = Math.max(top, value[i] + best(weight, value, rem - weight[i]));
17
        }
18
    }
19
    return top;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(nᵂ) timeO(W) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls4W = 0 — best(0) returns 0 immediately — nothing can be packed.Explore edge cases

Edge cases handled

W = 0best(0) returns 0 immediately — nothing can be packed.

Pitfalls

Advancing an item index in the recursion — that turns it into 0/1 and forbids reuse.
Forgetting the weight[i] <= rem guard — negative capacity subproblem.
Skipping this approach — interviewers want to hear the recurrence before the table.

03.2

Approach 2 of 3

Top-Down Memoization on Remaining Capacity

TimeO(nW)SpaceO(W)

The fix once you name the overlap — 'cache the best value for each remaining capacity'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

best(rem) returns the same answer every time. Where can you store it so each capacity is solved once?

2Hint 2Explore hint

Add a memo of size W+1 indexed by remaining capacity. Check on entry, fill before returning.

3Hint 3Explore hint

memo[rem] = max over fitting items of value[i] + best(rem - weight[i]); use -1 for 'uncomputed' since 0 is valid.

A · Core idea

Why -1 as sentinel. 0 is a legitimate best value (nothing fits), so it can't double as 'uncomputed'; initialize the memo to -1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

weight = [1, 3, 4, 5], value = [10, 40, 50, 70], W = 8

best(8)

needs best(7), best(5), best(4), best(3)

Statememo empty

Final result110

C · Code with teaching comments

solution.javaJava

Top-Down Memoization on Remaining Capacity — reference

4 teaching notes

1
public int unboundedKnapsack(int[] weight, int[] value, int W) {
2
    int[] memo = new int[W + 1];
3
    // -1 means 'uncomputed' — distinct from the valid best value 0.
4
    Arrays.fill(memo, -1);
5
    return best(weight, value, W, memo);
6
}
7
 
8
private int best(int[] weight, int[] value, int rem, int[] memo) {
9
    if (rem == 0) {
10
        return 0;
11
    }
12
    // Cache hit — return the stored best for this remaining capacity in O(1).
13
    if (memo[rem] != -1) {
14
        return memo[rem];
15
    }
16
    int top = 0;
17
    for (int i = 0; i < weight.length; i++) {
18
        if (weight[i] <= rem) {
19
            // Try every item; the recursion stays on the full menu, allowing reuse.
20
            top = Math.max(top, value[i] + best(weight, value, rem - weight[i], memo));
21
        }
22
    }
23
    // Store the resolved best before returning so this capacity is never recomputed.
24
    memo[rem] = top;
25
    return top;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(nW) timeO(W) spaceOpen the invariant and proofExplore the proof

ComplexityO(nW) time, O(W) space — There are W+1 distinct remaining-capacity states. Each does O(n) work scanning items → O(nW) time. The memo plus recursion stack is O(W).

E · Edge cases and pitfalls5W = 0 — best(0) = 0 immediately.Explore edge cases

Edge cases handled

W = 0best(0) = 0 immediately.
no item fits WLoop adds nothing; memo[W] = 0 → answer 0.

Pitfalls

Using 0 as 'uncomputed' — collides with the valid answer 0; use -1.
Indexing the memo at W instead of W+1 entries — capacities 0..W need W+1 slots.
Deep recursion in Python (rem up to W) can blow the ~1000 recursion limit — prefer tabulation for large W.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — 1-D dp[] Table, Capacity ASCENDING (Optimal)

TimeO(nW)SpaceO(W)

The answer they want. Frame it as 'fill dp[0..W] ascending; reuse is what the ascending sweep gives you for free'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Compute the best value for capacity 1, then 2, ... up to W, reusing earlier answers.

2Hint 2Explore hint

dp[w] = best value within capacity w. dp[0] = 0; for each w try every fitting item: dp[w] = max(dp[w], value[i] + dp[w - weight[i]]).

3Hint 3Explore hint

Sweep w ASCENDING. Because dp[w - weight] is already finalized AND may itself include item i, the same item gets reused automatically — the opposite of 0/1's descending sweep.

A · Core idea

Why dp[0] = 0 anchors everything. Every reachable capacity's value is built from dp[0] through a chain of item additions. Leave dp[0] unset and no capacity could be relaxed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

weight = [2, 3], value = [5, 8], W = 6

Array state

init

dp[0]=0, rest 0

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result16

C · Code with teaching comments

solution.javaJava

Bottom-Up — 1-D dp[] Table, Capacity ASCENDING (Optimal) — optimal

4 teaching notes

1
public int unboundedKnapsack(int[] weight, int[] value, int W) {
2
    // dp[w] = best value within capacity w; defaults to 0, which is also the dp[0]
3
    // anchor.
4
    int[] dp = new int[W + 1];
5
    // ASCENDING capacities — dp[w - weight] is already final and may include this item,
6
    // enabling reuse.
7
    for (int w = 1; w <= W; w++) {
8
        for (int i = 0; i < weight.length; i++) {
9
            // Only relax with items that fit, so w - weight[i] is non-negative.
10
            if (weight[i] <= w) {
11
                // Take item i on top of the best fill of the remaining capacity. The
12
                // whole DP in one line.
13
                dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
14
            }
15
        }
16
    }
17
    return dp[W];
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(nW) timeO(W) spaceOpen the invariant and proofExplore the proof

ComplexityO(nW) time, O(W) space — The outer loop runs W times, the inner loop scans n items → O(nW) time. A single dp array of size W+1 → O(W) space, no recursion stack.

E · Edge cases and pitfalls6W = 0 — Outer loop never runs; dp[0] = 0 returned — empty knapsack.Explore edge cases

Edge cases handled

W = 0Outer loop never runs; dp[0] = 0 returned — empty knapsack.
single weight-1 itemdp[w] = w × value, packing W copies of the unit item.
no item fits WInner guard always fails; dp stays 0 → answer 0.

Pitfalls

Iterating capacity DESCENDING out of 0/1 habit — forbids reuse and undercounts the value.
Forgetting the weight[i] <= w guard — negative index into dp.
Confusing this with the COUNT-of-ways variant, where the item/capacity loop nesting changes the meaning.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Descending sweep kills reuse

Descending order keeps dp[w - weight] at its pre-item value, which is exactly 0/1 behavior. For unbounded you WANT dp[w - weight] to already include the item, so you must sweep ascending.

Explore the code comparison

Don't write this

for (int w = W; w >= 1; w--) {          // DESCENDING — 0/1 behavior
    for (int i = 0; i < weight.length; i++)
        if (weight[i] <= w)
            dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
}

Write this instead

for (int w = 1; w <= W; w++) {          // ASCENDING — allows reuse
    for (int i = 0; i < weight.length; i++)
        if (weight[i] <= w)
            dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
}

Advancing the item index in recursion

Recursing on i+1 (or shrinking the item list) forbids reusing an item — that's the 0/1 recurrence. Unbounded must recurse on the SAME item set.

Explore the code comparison

Don't write this

def best(i, rem):
    if i == len(weight) or rem == 0:
        return 0
    take = value[i] + best(i + 1, rem - weight[i])  # advances i — single use
    return max(best(i + 1, rem), take)

Write this instead

def best(rem):
    top = 0
    for i in range(len(weight)):
        if weight[i] <= rem:
            top = max(top, value[i] + best(rem - weight[i]))  # same menu
    return top

Sentinel collides with a valid 0

0 is a legitimate best value (nothing fits), so it can't also mean 'uncomputed'. Initialize the memo to -1.

Explore the code comparison

Don't write this

int[] memo = new int[W + 1]; // all 0
if (memo[rem] != 0) return memo[rem];

Write this instead

int[] memo = new int[W + 1];
Arrays.fill(memo, -1);
if (memo[rem] != -1) return memo[rem];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Unbounded knapsack — reusable items, 1-D table swept ASCENDING

Code pattern to memorize

dp[0] = 0
for w in 1..W:
    for each item i with weight[i] <= w:
        dp[w] = max(dp[w], value[i] + dp[w - weight[i]])
return dp[W]

Rules to remember

1Each item is reusable unlimited times — the take branch recurses on the same item set, never shrinking it.
2Iterate capacity ASCENDING (1 → W). That's the exact opposite of 0/1, and it's what lets dp[w - weight] already include the item you're adding again.
3It's a max of value: dp[w] = max(dp[w], value[i] + dp[w - weight[i]]).
4Anchor dp[0] = 0 — zero capacity yields zero value — and start every other cell at 0 (taking nothing is always allowed).
5Only relax dp[w] from a fitting item (weight[i] <= w) to avoid a negative index.

Use this pattern when

Maximize value/score under one capacity with items reusable any number of times
Choosing how many of each denomination/piece to use, repetition allowed
Order of selection doesn't matter, only the multiset of chosen items
Coin Change / Rod Cutting flavored problems (reuse permitted)

Choose another pattern when

Each item usable at most once → 0/1 knapsack, iterate capacity DESCENDING
You want the COUNT of ways to fill, not the max value → counting DP (loop order matters)
Capacity is astronomically large → O(nW) table infeasible, rethink with math/BFS
Fractions allowed → greedy fractional knapsack by ratio, no DP needed

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Coin Change
Unbounded knapsack minimizing the COUNT of items to hit an exact target — swap max-value for min-count.
Coin Change II
Coming soon
Count the NUMBER OF ways to fill the target with reusable coins — loop coins outer to avoid counting permutations.
Rod Cutting
Maximize price by cutting a rod — unbounded knapsack where a length-i piece is a reusable 'item' of weight i and value price[i].
Combination Sum IV
Coming soon
Count ordered sequences (permutations) summing to target — capacity outer, items inner.

Same pattern

←

Subset Sum

Continue · Next problem

0/1 Knapsack