Published by Dimitris Kougioumtzis · Updated
Move capacities forward so each item can be used any number of times.
Append an available item to a smaller-capacity optimum, allowing repeated copies to accumulate.
When to use Unbounded knapsack
Optimization with reusable items.
Choosing an alternative
0/1 knapsack forbids reuse and changes the update direction.
Worked example: input and state changes
Example input
2,3 | 3,4 | 6
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 0, 0, 0 ], "active": [] }Step 3: Capacity 3: try item 1; best value 4.
State at this checkpoint
{ "values": [ 0, 0, 3, 4, 0, 0, 0 ], "active": [ 3 ] }Step 5: Capacity 4: try item 1; best value 6.
State at this checkpoint
{ "values": [ 0, 0, 3, 4, 6, 0, 0 ], "active": [ 4 ] }Step 8: Capacity 6: try item 0; best value 9.
State at this checkpoint
{ "values": [ 0, 0, 3, 4, 6, 7, 9 ], "active": [ 6 ] }Step 10: Maximum unbounded knapsack value = 9.
State at this checkpoint
{ "values": [ 0, 0, 3, 4, 6, 7, 9 ], "active": [ 6 ] }
Expected final state
Maximum unbounded knapsack value = 9.
Complexity and input bounds
Family: Dynamic programming. Time complexity: O(items × capacity).
Space complexity: O(capacity) DP storage.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Weights | values | capacity. Equal lists of 1–16 positive integers (1–99); capacity 0–40.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Positive weights are essential: a zero-weight positive-value item would make the optimum unbounded.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 | // Equal-length positive weights/values arrays, n <= 16, capacity <= 40. Items may be reused. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(weights, values, n, capacity) { let dp = Array(256).fill(0); for (let c = 1; c <= capacity; c++) { for (let i = 0; i < n; i++) { if (weights[i] <= c) { let candidate = values[i] + dp[c - weights[i]]; if (candidate > dp[c]) { dp[c] = candidate; } } } } return dp[capacity]; } |
Source
Foundational dynamic-programming paper. It establishes the general method, not the first publication or exact recurrence of this particular teaching example.
- The theory of dynamic programming
Richard Bellman (1954). Foundational method paper.