Skip to main content
Z

Knapsack Visualizer — DP Table

Animated 0/1 knapsack dynamic programming — fills the DP table cell by cell, highlighting dependencies, with step controls. Runs in your browser.

Free No signup Client-side Privacy friendly Updated

/

Pseudocode

Press Run to animate the algorithm.

How to use

  1. 1 Press Run to fill the dynamic-programming table cell by cell.
  2. 2 Each row is an item; each column is a capacity from 0 to W.
  3. 3 A cell is the best of skipping the item (blue cell above) or taking it.
  4. 4 The bottom-right cell is the best achievable value. Shuffle for new items.

Why use this tool

  • See 0/1 knapsack solved by dynamic programming, not brute force.
  • Watch each cell built from the two cells it depends on.
  • Understand the O(n·W) running time versus exponential brute force.
  • Runs entirely in your browser. No signup, no uploads.

Frequently asked questions

What is the 0/1 knapsack problem?

Given items each with a weight and value and a capacity W, choose a subset (each item taken once or not at all) that maximizes total value without exceeding W.

How does the DP table work?

dp[i][w] is the best value using the first i items within capacity w. Each cell is max(skip the item = dp[i-1][w], take it = dp[i-1][w-wi] + vi).

What is the time complexity?

O(n·W) time and O(n·W) space (reducible to O(W)). This is pseudo-polynomial — efficient when W is small.

Why is it called 0/1 knapsack?

Each item is either fully taken (1) or left out (0) — you cannot take fractions, unlike the fractional knapsack which a greedy method solves.

What is 0/1 Knapsack Visualizer?

A 0/1 Knapsack Visualizer animates the dynamic-programming table where dp[i][w] is the best value using the first i items within capacity w, computed as max of skipping or taking each item. The bottom-right cell is the optimal value.

Features

DP table animation

Watch the value table fill in as each item and capacity are considered.

Complexity

Time & space: O(nW) (pseudo-polynomial). The problem is NP-hard in general.

100% private

Runs entirely in your browser — nothing is uploaded.

Example

Input

items (w,v) = (10,60),(20,100),(30,120); capacity 50

Output

max value = 220 (take items 2 and 3, weight 50)

Common use cases

  1. 1

    Learn dynamic programming

    See how overlapping subproblems build the optimal value.

  2. 2

    Resource allocation

    Model choosing items under a weight or budget limit.

  3. 3

    Pseudo-polynomial insight

    Understand why O(nW) isn't truly polynomial.

Summary

Zerethon's 0/1 knapsack visualizer animates the dynamic-programming solution in your browser, filling a table of best values by item and remaining capacity. It runs in O(nW) time and O(nW) space (n items, capacity W) — pseudo-polynomial, since W is exponential in its bit length; the 0/1 knapsack problem is NP-hard in general.

Category
Algorithm
Pricing
Free
Privacy
Browser-based
Signup
Not required

References

Privacy

Your data never leaves your browser unless explicitly stated. 0/1 Knapsack Visualizer runs entirely client-side — no server upload, no logging, no tracking of your input.

New to this? Read the step-by-step explanation with Big-O analysis: Learn Dynamic Programming →

Related tools

Bubble Sort Visualizer

Animated bubble sort with step controls, speed, custom input, live comparison/swap counters and pseudocode. Runs entirely in your browser.

Open tool

Insertion Sort Visualizer

Animated insertion sort with step controls, speed, custom input, live comparison/write counters and pseudocode. Runs in your browser.

Open tool

Selection Sort Visualizer

Animated selection sort with step controls, speed, custom input, live comparison/swap counters and pseudocode. Runs in your browser.

Open tool

Merge Sort Visualizer

Animated merge sort with step controls, speed, custom input, live comparison/write counters and pseudocode. Runs in your browser.

Open tool

Build, share, and grow on Zerethon Social

Free signup. Earn points, collect achievements, and connect with creators worldwide.

Try Zerethon free