How it works
Rolling Array
dp[w] = best value achievable using exactly capacity w. Starts all zeros, updated in-place per item.
dp = [0] * (W + 1)
Backwards Scan
For each item we iterate w = W → weight[i]. Going backwards prevents an item from being counted twice in one pass.
for w in range(W, wt-1, -1)
Include vs Exclude
Each slot: keep existing value (exclude) or take val + dp[w−wt] (include). We pick the max of the two.
dp[w] = max(dp[w], val+dp[w−wt])
Speed:
dp[ ] — one cell per capacity slot (w = 0 to W)
Explanation
—
Enter items above and click Visualize to step through the DP array.
How it works
Ratio Sort
Compute ratio = value / weight for each item. Sort in descending order — highest 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 entirely. No fractions.
if wt ≤ remaining: take
0/1 Caveat
Greedy is optimal for fractional knapsack. For 0/1 it can miss the global optimum — a lower-ratio item might unlock a better combination.
not always globally optimal
Speed:
Remaining Capacity
Used: 0Remaining: —Total: —
Items sorted by value / weight ratio
Explanation
—
Enter items above and click Visualize.
How it works
Recursion
For every item, split into two recursive calls: include it or exclude it. Returns the max of both branches.
f(n,W) = max(excl, incl)
Base Cases
Return 0 when items run out (n=0) or capacity is zero (W=0). Force-skip if item is too heavy.
if n==0 or W==0: return 0
Exponential Cost
Each item doubles the tree — 2ⁿ leaf nodes total. n=20 means 1M+ calls. This is why DP exists: memoize the overlapping subproblems.
2^n total subproblems
Speed:
Recursion tree — DFS order. Each node shows (value so far, remaining capacity)
Explanation
—
Enter items above and click Visualize. Recommend n ≤ 5.