Fractional Knapsack
The fractional knapsack problem presents a thief with a bag of capacity W and n items, each with a weight w[i] and value v[i]. Unlike the 0/1 variant, the ...
Problem Definition and Greedy Strategy
The fractional knapsack problem presents a thief with a bag of capacity W and n items, each with a weight w[i] and value v[i]. Unlike the 0/1 variant, the thief may take any fraction of an item. The goal is to maximize total value without exceeding capacity W.
The greedy strategy is to compute the value-per-unit-weight ratio v[i]/w[i] for each item, sort items by this ratio in descending order, then greedily fill the knapsack. Take as much of the highest-ratio item as possible before moving to the next. If the knapsack still has space after exhausting an item, move to the next highest-ratio item. If the last item does not fit entirely, take the fraction that fills the remaining capacity.
A worked example: capacity W = 50, items with (weight, value) — (10, 60), (20, 100), (30, 120). Ratios: 6.0, 5.0, 4.0. Take all 10 units of item 1 (value 60, remaining capacity 40). Take all 20 units of item 2 (value 100, remaining capacity 20). Take 20 of 30 units of item 3 (value 80, remaining capacity 0). Total value = 60 + 100 + 80 = 240. This is the maximum achievable.
Time complexity is O(n log n) for sorting and O(n) for the greedy pass, giving O(n log n) overall. Space complexity is O(1) auxiliary.
Interview tip: Explicitly distinguish fractional from 0/1 knapsack at the start of your answer. Greedy is optimal for fractional but not for 0/1. This distinction is the single most common follow-up question interviewers ask about knapsack problems.
Why Greedy Fails for 0/1 Knapsack
The greedy ratio approach fails for 0/1 knapsack because you cannot take fractions. Consider capacity W = 10 and items with (weight, value) — (6, 12), (5, 10), (5, 10). Ratios are 2.0, 2.0, 2.0 — all equal. Greedy picks item 1 (weight 6, value 12), then tries item 2 (weight 5), but 6 + 5 = 11 > 10. It stops with value 12. The optimal solution is to take items 2 and 3 (weights 5 + 5 = 10, value 20). Greedy missed the better solution by committing to the first item.
A more striking counterexample: capacity W = 10, items — (10, 10), (6, 7), (5, 6). Ratios: 1.0, 1.167, 1.2. Greedy picks the item with ratio 1.2 (weight 5, value 6), then item with ratio 1.167 (weight 6, value 7), but 5 + 6 = 11 > 10, so only item 3 fits (value 6). Optimal is item 1 alone (value 10). Greedy gives 6; optimal gives 10.
This failure occurs because greedy commits to local choices that block better global combinations. The 0/1 constraint creates combinatorial dependencies between choices that the ratio alone cannot capture. Dynamic programming is needed to consider all combinations efficiently through memoization or tabulation, achieving O(nW) time.
Interview tip: Prepare both counterexamples above. Being able to produce a concrete small counterexample in under a minute, rather than just asserting that greedy fails, is a strong signal of algorithmic depth during technical interviews.
Implementation Details and Edge Cases
Implementing fractional knapsack correctly requires handling several edge cases. First, sort items by ratio descending; use a stable sort if you want deterministic behavior when ratios tie. Second, use floating-point arithmetic carefully — when computing fractions, the accumulated value may have small rounding errors. For competitive programming, you may need to output with sufficient decimal precision, typically six decimal places.
Edge case 1: all items fit in the knapsack. In this case, the greedy loop terminates naturally after taking every item completely, and total weight equals the sum of all weights, which is at most W. Return the sum of all values.
Edge case 2: a single item weighs more than the entire knapsack. You still take a fraction of it: value contributed is v[i] * (W / w[i]).
Edge case 3: capacity W is zero. Return 0 immediately without entering the main loop.
Pseudocode: sort items by v[i]/w[i] descending. Set remaining = W, total_value = 0. For each item in sorted order: if item.weight <= remaining, take whole item, remaining -= item.weight, total_value += item.value. Else, take fraction: total_value += item.value * (remaining / item.weight), remaining = 0, break. Return total_value.
For very large n (millions of items), memory layout matters. Storing items as structs with weight and value contiguously is more cache-friendly than storing them in separate arrays. This reduces cache misses during the sort and the linear pass.
Interview tip: Mention that in production code you would validate inputs (non-negative weights and values, positive capacity) before running the algorithm. Input validation is a mark of engineering discipline that pure algorithm knowledge alone does not demonstrate.