⚠️ This visualization was AI-generated and may contain inaccuracies. The 0/1 Knapsack is a classic CS problem — please verify against standard references.

🎒 0/1 Knapsack

An interactive visualization of the classic 0/1 Knapsack dynamic programming algorithm. Watch the 2D DP table fill as we decide whether to take or skip each item to maximize value within a weight capacity.

Dynamic Programming Classic Medium

The Problem

Given n items, each with a weight and a value, and a knapsack with a maximum weight capacity W, find the maximum value that can be carried in the knapsack.

Each item can be taken at most once (0/1 decision).

Example: Items with weights [2, 3, 4, 5] and values [3, 4, 5, 6], capacity W=8.
Best: take items 2 and 3 (weights 2+3=5, values 3+4=7) or items 0 and 3 (weights 2+5=7, values 3+6=9). The maximum is 9.

Interactive Visualization

Items (weight:value pairs)

Capacity

Preset

Speed:

Items (Capacity: 8)

DP Table: dp[item][weight]

Status

Press Step or Play to begin.

Code

fun knapsack(weights: IntArray, values: IntArray, capacity: Int): Int {    val n = weights.size    val dp = Array(n + 1) { IntArray(capacity + 1) }    for (i in 1..n) {        for (w in 0..capacity) {            dp[i][w] = dp[i - 1][w]  // skip item            if (weights[i - 1] <= w) {                dp[i][w] = maxOf(                    dp[i][w],                    dp[i - 1][w - weights[i - 1]] + values[i - 1]                )    }   }   }    return dp[n][capacity]}

def knapsack(weights, values, capacity):    n = len(weights)    dp = [[0] * (capacity + 1) for _ in range(n + 1)]    for i in range(1, n + 1):        for w in range(capacity + 1):            dp[i][w] = dp[i-1][w]  # skip item            if weights[i-1] <= w:                dp[i][w] = max(                    dp[i][w],                    dp[i-1][w - weights[i-1]] + values[i-1]                )    return dp[n][capacity]

How It Works

State Definition

dp[i][w] = maximum value achievable using the first i items with capacity w.

Recurrence Relation

For each item i and capacity w, we have two choices:

Skip item i: dp[i][w] = dp[i-1][w] (inherit value from previous row)
Take item i: dp[i][w] = dp[i-1][w - weight[i-1]] + value[i-1] (if weight[i-1] ≤ w)

We take the maximum of these two options. The base case is dp[0][w] = 0 (no items = zero value).

The Algorithm

Initialize: Create a 2D table of size (n+1) × (capacity+1), filled with zeros.
Fill the table: For each item i (1 to n) and each weight w (0 to capacity):
- Start by copying the value from the row above (skip the item).
- If the item's weight fits (weight[i-1] ≤ w), calculate the value of taking it.
- Store the maximum of skip and take.
Result: dp[n][capacity] holds the maximum value.
Backtrack (optional): Trace back through the table to find which items were selected.

Complexity

Time O(n × W)

Space O(n × W)

Where n is the number of items and W is the knapsack capacity. This is pseudopolynomial time because it depends on the numeric value of W, not its input size (log W). The space can be optimized to O(W) using a 1D rolling array, but the 2D version is clearer for visualization.