Published by Dimitris Kougioumtzis · Updated
Process capacities backward so each item can be used at most once.
Compare taking or skipping each indivisible item; descending capacity updates prevent using that item twice.
When to use 0/1 knapsack
Selection under a small integer capacity.
Choosing an alternative
Unbounded knapsack permits reuse and changes the update order.
Worked example: input and state changes
Example input
2,3,4 | 3,4,5 | 5
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 ], "active": [] }Step 3: Item 0: weight 2, value 3; capacity 3 best value 3.
State at this checkpoint
{ "values": [ 0, 0, 0, 3, 3, 3 ], "active": [ 3 ] }Step 5: Item 1: weight 3, value 4; capacity 5 best value 7.
State at this checkpoint
{ "values": [ 0, 0, 3, 3, 3, 7 ], "active": [ 5 ] }Step 8: Item 2: weight 4, value 5; capacity 5 best value 7.
State at this checkpoint
{ "values": [ 0, 0, 3, 4, 4, 7 ], "active": [ 5 ] }Step 10: Maximum knapsack value = 7.
State at this checkpoint
{ "values": [ 0, 0, 3, 4, 5, 7 ], "active": [ 5 ] }
Expected final state
Maximum knapsack value = 7.
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 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
Ascending in-place updates solve a different reuse model; capacity-based bounds are pseudopolynomial.
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 | // Equal-length positive weights/values arrays; n ≤ 16 and capacity ≤ 40. Each item is used at most once. 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 i = 0; i < n; i++) { for (let c = capacity; c >= 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.