0/1 Knapsack Visualizer

Explore 0/1 Knapsack decisions through an interactive dynamic programming table, selected items, state transitions, and optimal value.

Current status: Ready. Use the controls to begin exploring 0/1 Knapsack.

0/1 Knapsack Problem Visualizer

item \ w012345678
∅
0
0
0
0
0
0
0
0
0
#1 (2:3)
0
0
0
0
0
0
0
0
0
#2 (3:4)
0
0
0
0
0
0
0
0
0
#3 (4:5)
0
0
0
0
0
0
0
0
0
#4 (5:6)
0
0
0
0
0
0
0
0
0

Base case: 0 items or 0 capacity always yields value 0.

Step 1 / 73

Animation Legend

Dependency Cell(s)
Cell Being Computed
Filled Cell

For each item and capacity, the algorithm compares including the item (previous row's value at the remaining capacity plus this item's value) against excluding it (previous row's value at the same capacity), and keeps the larger result.

Java Implementation

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                int include = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                int exclude = dp[i - 1][w];
                dp[i][w] = Math.max(include, exclude);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

What is the 0/1 Knapsack Problem?

The 0/1 Knapsack Problem asks: given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, which items should be chosen to maximize the total value without exceeding the capacity? Each item can either be taken whole or left behind entirely - it cannot be split, hence "0/1".

A brute-force solution would try every possible subset of items, giving O(2^n) time complexity. Dynamic Programming avoids this by building a table where dp[i][w] represents the best value achievable using the first i items with capacity w, reusing previously solved subproblems just like in the Fibonacci Sequence visualizer.

Time & Space Complexity

  • Brute ForceO(2^n)
  • DP TimeO(n · W)
  • DP SpaceO(n · W)
  • Optimized SpaceO(W)

* n = number of items, W = knapsack capacity. This is "pseudo-polynomial" because it depends on the magnitude of W, not just the input size.

Real-World Use Cases

  • ✓
    Resource AllocationChoosing projects or investments under a fixed budget to maximize return.
  • ✓
    Cargo & LogisticsLoading shipments to maximize value while respecting weight limits.
  • ✓
    Memory-Constrained SystemsSelecting which assets or features to load within a fixed memory budget.

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

0/1 Knapsack Problem Complete Info Card

Dynamic ProgrammingPseudo-Polynomial

The 0/1 Knapsack Problem fills a 2D table where each cell dp[i][w] represents the maximum value achievable using the first i items with capacity w, comparing whether including or excluding the current item is more valuable.

Algorithm Characteristics

Time Complexity (Brute Force)

Tries every possible subset of items

O(2^n)

Time Complexity (DP)

n items, W = knapsack capacity

O(n · W)

Space Complexity (DP)

Full 2D table of items vs. capacity

O(n · W)

Space Complexity (Optimized)

Single rolling row, iterated right to left

O(W)

Optimal Substructure

Best value at dp[i][w] built from dp[i-1]

Yes

Problem Type

Each item taken whole or not at all

0/1

DP Table Fill Steps

1

Initialize dp[0][w] = 0 for all capacities

2

For each item, iterate over every capacity

3

If item fits, compare include vs exclude

4

include = value + dp[i-1][w-weight]

5

exclude = dp[i-1][w]

6

dp[i][w] = max(include, exclude)

Optimization Techniques

1D Rolling Array

Iterate capacity right-to-left to reuse one row

for (w = W; w >= weight; w--)

Backtracking

Trace dp[i][w] vs dp[i-1][w] to recover chosen items

if (dp[i][w] != dp[i-1][w]) select item i

When to Use

  • •Resource allocation under a fixed budget or capacity
  • •Item count and capacity are small to moderate
  • •Each item is indivisible (whole or nothing)

When to Avoid

  • •Extremely large capacity W (table grows too large)
  • •Items can be fractionally split (use Fractional Knapsack greedy instead)
  • •Brute-force subsets for more than ~20 items
Did You Know? The Knapsack Problem is NP-complete in general, but the DP solution runs in pseudo-polynomial time because it depends on the numeric value of W.
Resource allocation2D DP tableBacktracking