0/1 Knapsack Visualizer

What is 0/1 Knapsack Visualizer?

0/1 Knapsack Visualizer fills the dynamic-programming table one cell at a time, and for each cell it shows the two candidates it is choosing between: skip this item and inherit the value above, or take it and add its value to the best solution for the remaining capacity. The arrows to the exact cells being read are the part that makes DP click — the recurrence stops being a formula and becomes two specific cells you can point at.

Recommended workflow

1. 1

   Compare with the greedy version

   Fractional knapsack is solvable greedily — see why 0/1 is not.

   Open tool
2. 2

   Another classic DP table

   Coin change fills a table with the same skip-or-take shape.

   Open tool
3. 3

   DP on two sequences

   Longest common subsequence builds a 2-D table from two strings.

   Open tool

Frequently asked questions

Why can't I just take the best value-per-weight items first?

That greedy strategy is optimal for fractional knapsack, where you can take part of an item. In 0/1 an item is all or nothing, and greedy can fill the bag with a good item that blocks a better combination.

How do I know which items were chosen?

Start at the bottom-right cell and walk up. If a cell's value equals the one directly above it, that item was skipped; if not, it was taken — subtract its weight and continue from that row and column.

What is the complexity?

O(n × W) time and space for n items and capacity W. That is pseudo-polynomial: it scales with the numeric value of the capacity, not with the number of bits used to write it down.

Can the space be reduced?

Yes. Each row only reads from the row above, so a single array iterated right to left is enough — O(W) space. You lose the ability to trace back the chosen items, which is why the full table is shown here.