Dynamic Programming — 0/1 Knapsack
The table and its shadow.
The 2D table is the classic formulation. The 1D array is its space-optimized form — both produce the same answer. Watch them fill in sync.
O(n·W) time · 2D: O(n·W) space · 1D: O(W) space · Globally Optimal
How they relate
2D Table (Classic)
dp[i][w] = best value using first i items with capacity w. Each row builds on the row above.
dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]])
1D Array (Optimized)
Reuses a single row, overwriting in-place. Backwards scan ensures we read the previous item's values, not the current one's.
dp[w] = max(dp[w], val[i] + dp[w-wt[i]])
The Connection
At step i, the 1D array equals row i of the 2D table. The highlighted cells always match. Same answer, less memory.
dp1D[w] ≡ dp2D[i][w] at all times
Speed:
dp[i][w] — 2D table
Classic O(n·W)
dp[w] — 1D array
Optimized O(W)
Sync note
Run the visualization to see how the 1D array mirrors the current row of the 2D table at every step.
Step Explanation
—
Enter items above and click Visualize to step through both tables in sync.
Greedy — 0/1 Knapsack
Best ratio first.
Sort items by value/weight ratio and greedily take the highest-efficiency items that fit. Fast but not guaranteed optimal for 0/1.
O(n log n) time · O(n) space · Approximation
How it works
Ratio Sort
Compute ratio = value / weight for each item. Sort descending — max bang-per-unit-weight first.
sorted by v/w descending
Greedy Pick
Walk the sorted list. If an item fits in remaining capacity → take it whole. Otherwise → skip. No fractions.
if wt ≤ remaining: take
0/1 Caveat
Optimal for fractional knapsack. For 0/1, a lower-ratio item might unlock a globally better combination.
not always globally optimal
Speed:
Remaining Capacity
Used: 0Remaining: —Total: —
Items — sorted by value / weight ratio
Step Explanation
—
Enter items above and click Visualize.
Brute Force — 0/1 Knapsack
Try everything.
Exhaustive recursion exploring every include/exclude branch. Guaranteed optimal — but the search space doubles with each item.
O(2ⁿ) time · O(n) space · Optimal · Recommend n ≤ 5
How it works
Recursion
For every item, branch into two calls: include or exclude. Return the maximum of both branches.
f(n,W) = max(excl, incl)
Base Cases
Return 0 when n=0 (no items) or W=0 (no capacity). Force-skip if item is too heavy.
if n==0 or W==0: return 0
Exponential Cost
Each item doubles the tree — 2ⁿ leaves. DP eliminates redundancy by memoizing overlapping subproblems.
2^n total combinations
Speed:
Recursion tree — DFS order · node = (value so far, remaining capacity)
Step Explanation
—
Enter items and click Visualize. Keep n ≤ 5 for readable tree.