Unbounded Knapsack

Fill capacities while allowing each item to be chosen repeatedly, exposing the loop-order difference from 0/1 Knapsack.

Core idea

Each item type may be chosen repeatedly. When a state takes the current item, its remainder stays on the same row instead of moving to the previous-item row.

Read the visualization

Every matrix cell compares skipping the item with taking one copy plus the best value at the smaller capacity. The highlighted dependency reveals why reuse is allowed.

	1	2	3	4	5	6
∅	0	0	0	0	0	0
A
B
C

Initialize zero value for every capacity before considering any item type.

1function completeKnapsack(w: number[], v: number[], W: number): number {
const m = w.length;
const dp = Array.from({ length: m + 1 }, () => Array(W + 1).fill(0));
for (let i = 1; i <= m; i++) {
  for (let c = 1; c <= W; c++) {
    if (w[i - 1] > c) {
      dp[i][c] = dp[i - 1][c];
    } else {
      dp[i][c] = Math.max(
        dp[i - 1][c], dp[i][c - w[i - 1]] + v[i - 1]); //  take cell choose current row  i
    }
  }
}
return dp[m][W];
15}

capacity6

itemA( duplicate 2, value 5) B( duplicate 3, value 6) C( duplicate 4, value 7)

1 / 20

Complexity and tradeoffs

Time: O(nW). Space: O(nW). A one-dimensional table uses O(W) space when capacities iterate upward for reusable items.

Invariant: After finishing item row i, every capacity stores the best value obtainable from unlimited copies of the first i item types.

Where it fits

Unbounded Knapsack models repeatable purchases, cutting, and resource composition. Reverse the one-dimensional capacity loop to recover the at-most-once 0/1 variant.

Algorithm Visualizer

Unbounded Knapsack

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits