Medium Problemsknapsackoptimization

Unbounded Knapsack

Given n item types, each with a weight and a value, and a knapsack with a fixed weight capacity, choose items to fill it, where any type may be reused any number of times, to maximize total value without exceeding the capacity.

Do this lesson first: coin change

Example input

item types as (weight, value) = (2, 3), (3, 5), (5, 9); capacity = 6; any type may be taken again

Expected output

10

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][c] = max(dp[i - 1][c], v_i + dp[i][c - w_i]), the second only when w_i <= c

Ask whether the best load uses type i at all. If not, it is the best from the first i - 1 types, the cell above. If it does, take one copy out: that copy was worth v_i, and what remains is a best load in c - w_i in which type i is STILL available, because there may be more copies of it. That is the cell w_i columns to the left in the SAME row, not the row above. That row index is the only thing that differs from zero-one-knapsack's recurrence, whose take option reads the row above because an item cannot go in twice. cutting-a-rod is this exact recurrence with piece lengths as the types.

Tabulation over (types + 1) × (capacity + 1) cells. One row is enough, swept UPWARD: for each type, for c from w up to the capacity, best[c] = max(best[c], v + best[c - w]). Upward is exactly what lets a type be reused, since best[c - w] may already include it. That is zero-one-knapsack's one-row loop with the direction flipped, which is why getting the direction wrong in either one silently solves the other problem. Here the two loops can also be swapped, capacity outside and types inside, without changing the answer, because a max does not care in which order the copies were added.

Time O(types × capacity)Space O(types × capacity), reducible to O(capacity) with one row swept upward

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 is the only base row: with no types allowed nothing is carried, so it is 0 at every capacity. Columns 0 and 1 compute and stay 0, since every type here weighs at least 2. Fill row by row and left to right within a row. The take option reads its own row further left, so that cell has to be final first, and a left-to-right sweep is what makes it so.

Rows ↓
Cols →

0

1

2

3

4

5

6

none

0

w2 v3

0

3

6

9

w3 v5

0

3

5

6

8

10

w5 v9

0

3

5

6

9

10

Rows ↓row i: may use the first i types

Cols →capacity c: best value that fits

unbounded-knapsack.ts

1function unboundedKnapsack(weights, values, capacity) {
2 const n = weights.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
4 // row 0: no item types, so value 0 at every capacity
5 for (let i = 1; i <= n; i++) {
6 const w = weights[i - 1], v = values[i - 1];
7 for (let c = 0; c <= capacity; c++) {
8 dp[i][c] = dp[i - 1][c];
9 if (w <= c) dp[i][c] = Math.max(dp[i][c], v + dp[i][c - w]);
10 }
11 }
12 return dp[n][capacity];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

unbounded-knapsack.ts

1function unboundedKnapsack(weights, values, capacity) {
2 const n = weights.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
4 // row 0: no item types, so value 0 at every capacity
5 for (let i = 1; i <= n; i++) {
6 const w = weights[i - 1], v = values[i - 1];
7 for (let c = 0; c <= capacity; c++) {
8 dp[i][c] = dp[i - 1][c];
9 if (w <= c) dp[i][c] = Math.max(dp[i][c], v + dp[i][c - w]);
10 }
11 }
12 return dp[n][capacity];
13}

Where people go wrong

Reading the take option from the row above. That allows each type once and returns zero-one-knapsack's answer: 9 at capacity 6, from the (5, 9) alone, against the true 10 from two (3, 5)s. In the one-row form the same mistake is sweeping capacity downward. Both versions run and return a plausible number, and they agree with the right answer wherever the optimum happens to use each type at most once (capacity 5 here, where both say 9), so a test at the wrong capacity passes.

Allow each item at most once.
That is zero-one-knapsack: the take option reads the row above, dp[i - 1][c - w_i]. State, max and fill order stay.
Cap each type at k copies.
Neither row works alone, since one says once and the other says without limit. Either list each type k times as separate 0/1 items, or split its copies into bundles of 1, 2, 4 and so on plus a last bundle of whatever remains (10 becomes 1, 2, 4 and 3), so about log k bundles make every count from 0 to k and none above it. Each bundle is one 0/1 item with that many times the weight and value, the take option then reads the row above as in zero-one-knapsack, and the max stays.
Count the ways to fill exactly capacity c instead of maximizing value.
That is coin-change-count-ways: the values drop out, a sum replaces the max, and row 0 becomes 1 at capacity 0 and 0 elsewhere. The same-row read stays, because a coin can be used again just as an item type can. The loop swap from the execution panel does not carry over: with a sum, putting capacity outside counts orderings, not combinations.

Printing Items in 0/1 Knapsack Word Break Problem