0/1 knapsack: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

0/1 knapsack example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. Step 0: Initial state.

    State at this checkpoint
    {
      "values": [
        0,
        0,
        0,
        0,
        0,
        0
      ],
      "active": []
    }
  2. 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
      ]
    }
  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
      ]
    }
  4. 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
      ]
    }
  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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 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.