The site's eighth dynamic programming entry, and the
closest sibling 0/1 Knapsack has on this site. Same setup —
items with a weight and a value, a knapsack with a fixed capacity, maximize total value without
going over — except here the supply of each item is unlimited: take a Pouch twice,
or four times, if that beats taking one of everything. 0/1 Knapsack's own Pitfalls section already
names this exact problem, as a warning: compress that page's table to a single row of size
capacity + 1, then fill the capacity loop upward instead of downward, and
"item i silently gets used a second time in the same pass — turning 0/1 knapsack into
the different (and easier) unbounded-knapsack problem." This page is that flip, done on purpose.
Four fixed items for a resupply cache — Bar (weight 1, value 1),
Pouch (weight 4, value 7), Canister (weight 5, value 10),
Coil (weight 7, value 13) — and a capacity of 8. Press
Step or Run to watch the single-row table fill in, one item at a
time, each item's pass allowed to build on cells its own earlier passes already improved. Once the
row is full, the demo backtracks from dp[8] to recover an actual optimal combination —
repeats and all.
dp[w] — best value achievable with capacity w
dp[w] holds the best total value reachable with capacity exactly w or
less, using any of the items, any number of times. The base case is dp[0] = 0 — no
capacity, no value, no choice available. For every larger w, the recurrence tries every
item that fits and keeps the best:
dp[w] = max over items i with weight[i] <= w of:
value[i] + dp[w - weight[i]]That's the same either/or shape 0/1 Knapsack's own recurrence uses per item — except there's no
"which items have been decided so far" axis here at all, because there's nothing to decide once:
an item is either usable at this capacity or it isn't, full stop, regardless of whether it already
appeared in the best answer for some smaller capacity. dp[w - weight[i]] is always a
strictly smaller capacity than w, so filling the row in increasing order of
w guarantees it's already finalized by the time anything needs to read it — including,
when that smaller capacity's own best answer already used item i, which is exactly how
reuse happens: not a special case, just an ordinary read of an already-correct smaller cell that
happens to have used the same item.
Item loop on the outside, capacity loop ascending on the inside — 0/1 Knapsack's row-compression trick, with the one loop-direction flip its Pitfalls section calls out:
function unboundedKnapsack(items, capacity) {
const dp = new Array(capacity + 1).fill(0);
const choice = new Array(capacity + 1).fill(-1); // which item last improved dp[w]
for (let idx = 0; idx < items.length; idx++) {
const { weight, value } = items[idx];
for (let w = weight; w <= capacity; w++) { // ascending, not descending
const candidate = dp[w - weight] + value;
if (candidate > dp[w]) {
dp[w] = candidate;
choice[w] = idx;
}
}
}
// backtrack from the full capacity, allowing the same item to repeat
let w = capacity;
const chosen = [];
while (w > 0 && choice[w] !== -1) {
const idx = choice[w];
chosen.push(items[idx]);
w -= items[idx].weight;
}
return { maxValue: dp[capacity], chosen };
}Greedily taking the best value-per-weight ratio, as many times as it fits, doesn't reach
the optimum here either — a different failure than 0/1 Knapsack's own ratio-greedy pitfall, since
indivisibility isn't the culprit this time; reuse is already allowed, which is exactly what ratio-
greedy needs to work for Fractional Knapsack. On
this page's demo data, Canister has the best ratio (10/5 = 2.0), ahead of Coil
(13/7 ≈ 1.857), Pouch (7/4 = 1.75), and Bar (1/1 = 1.0).
Taking one Canister first leaves 3 capacity — too little for another Canister, Coil, or
Pouch — filled out with 3 Bars for a total of 13. The table's real optimum
is 14: the best ratio locally is still a locally greedy choice, and locking in an early
pick can strand capacity that a lower-ratio combination would have used better.
The optimal value can be reached by more than one combination, and which one this page's
own backtrack recovers depends on loop order, not just on the data. Two different
combinations both total the true optimum of 14 at capacity 8: two Pouches
(4+4 weight, 7+7 value) or one Bar plus one Coil (1+7 weight,
1+13 value) — confirmed by brute force over every combination up to capacity
8, not just these two. The reference implementation above, item-outer with capacity
ascending, backtracks to two Pouches. Running the identical recurrence with the
loop order this site's own Coin Change page uses instead
— capacity outer, items inner — reaches the same dp[8] = 14 but backtracks to
Bar + Coil, a genuinely different answer, checked directly rather than assumed. Same
shape as 0/1 Knapsack's own tie pitfall: the number
is never ambiguous, but here even the loop's shape, not just how ties are broken within one
fixed shape, can change which reconstructed answer comes out.
Time: O(n · W) — n items, W + 1 capacities,
one constant-time comparison per pair, the same bound as 0/1 Knapsack and equally pseudo-polynomial for
the same reason: it scales with the numeric size of the capacity, not the size of its
representation. Space: O(W) — and unlike 0/1 Knapsack, that's not a
compression trade-off that costs the ability to backtrack. 0/1 Knapsack needs the full
O(n · W) table to recover which items were chosen, because reconstruction has to track
which items have already been decided; a single row loses that axis and with it the
backtrack. Here there's no such axis to lose — an item is equally available at every step regardless
of what's already been chosen — so the same O(W) row plus a same-sized choice
array reconstructs an actual optimal combination every time, at no extra space cost at all.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.