Interactive Lab · DSA & Algorithms
You have a bag that holds W kilos and a few items, each with a weight and a value. Each item is all or nothing: you take it whole or leave it. What's the most value you can carry? The tempting shortcut is greedy: grab the best value-per-kilo first. It sounds airtight. It's wrong. The fix is a dp table: dp[i][w] = the best value using only the first i items in a bag of size w. Each cell asks one question, skip item i, or take it?, and answers it from the row above. Fill it, trace back, and watch greedy lose.
▶ Setup, the items and the bag
Up to 8 items, weights 1–10, values 1–99. Rows tinted blue are the ones greedy-by-ratio grabs.
▶ The playground, fill the table row by row, then trace back the answer
0/1 knapsack is the template for every “pick a subset under a budget” question: choosing which features fit a sprint, which ads fill a slot, which jobs fit a server's RAM, which investments fit a cap. In interviews it unlocks a whole family: subset sum, partition equal subset, target sum, last stone weight II are all this exact table with the values tweaked. The take-or-skip recurrence you just watched is also the step from plain recursion to DP: same choices, each answered once.
The code that's actually running, a take-or-skip table, then a trace back
Hit ↺ classic example: capacity 10, items A (2 kg, ₹12), B (4 kg, ₹20), C (6 kg, ₹24). Greedy ranks by ₹/kg, A (6) > B (5) > C (4), so it packs A + B = 6 kg for ₹32 and has 4 kg left that nothing else fits. Predict: what does the table's corner dp[3][10] say, and which items does the trace back pick? (B + C = 10 kg exactly, ₹44, greedy's “best ratio” item A doesn't even make the cut.) Then press 💥 find a case greedy gets wrong a few times. Notice the pattern: greedy fails when its high-ratio picks leave wasted space that a cleverer combination would have filled.
The takeaway
dp[i][w] = max(dp[i−1][w], vi + dp[i−1][w − wti]): skip item i (same bag, one fewer item) or take it (its value plus the best you can do with the space left). That's the whole algorithm.i−1, so the table fills top to bottom, left to right, and each subproblem is solved exactly once: O(n·W) time instead of O(2ⁿ) subsets.dp[n][W] is the best value. Walk back up: if a cell differs from the one above it, that item was taken; jump left by its weight and keep going.w from W down to wt (right to left), so each item is used at most once. Loop left to right instead and you've written the unbounded knapsack.