Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
You can take fractions of items, so the answer is purely greedy: compute each item's value-to-weight ratio, take items in descending ratio order, and when the next item doesn't fit, take the fraction of it that fills the remaining capacity. Sorting by ratio costs O(n log n); the fill is one linear pass. The fractional twist is exactly what makes greedy optimal here — the 0/1 version (no fractions) is NP-hard and needs DP.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you sort by the value/weight RATIO (not raw value or raw weight), realise that divisibility lets exactly one item be split, and can justify the greedy with an exchange argument.
Where candidates slip
Sorting by highest value or lowest weight instead of best ratio, or forgetting to take the fraction of the last item that only partially fits.
How to stand out
State the exchange argument: if any capacity is spent on a lower-ratio item while a higher-ratio item is available, swapping a unit of weight toward the higher ratio strictly increases value — so the optimal solution must be greedy by ratio. Then contrast with 0/1 Knapsack to show you know why fractions matter.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMaximise value under a weight budgetCan items be split into fractions?YesNo (all-or-nothing)Explore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Repeated Max-Ratio Selection (Baseline)
1Hint 1Explore hintHide hint
Since you can split items, ask: if you had one more unit of capacity, which item would you spend it on? The one with the most value per unit weight.
2Hint 2Explore hintHide hint
That suggests always consuming the highest value/weight item available. How do you find it without sorting?
3Hint 3Explore hintHide hint
Scan all remaining items each round to find the max ratio, take it (whole or the final fraction), mark it used, and repeat until capacity is 0 or items run out.
A · Core idea
Build the answer by repeatedly grabbing the densest material. Each round, scan every not-yet-taken item, pick the one with the highest value/weight ratio, and either take it whole (if it fits the remaining capacity) or take the fraction that exactly fills what's left and stop.
Why per-unit value is the only thing that matters. Because items split, a unit of capacity isn't tied to any particular item — you can always spend it on whatever material gives the most value per unit weight. So the decision at every moment is identical: among what's left, which item has the best value/weight? Take from that one. There's no interaction between items beyond competing for the same capacity, which is what makes a one-item-at-a-time greedy correct.
Why the last item is the only fractional one. As long as the current best item fits entirely, taking it whole is never worse than taking part of it — you'd just have to fill the rest with something of equal-or-lower ratio. So you take wholes until an item doesn't fit, then take exactly the fraction of that item needed to reach capacity. That single partial take is always the final action.
Why we don't ship this. Re-scanning all items every round to find the max ratio is O(n²). The fix is obvious once you see the pattern: the rounds always want items in descending ratio order, so just sort once and walk the list. That's the optimal approach.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
value = [60, 100, 120], weight = [10, 20, 30], W = 50round 1
scan → max ratio is item0 (6); weight 10 ≤ 50 → take whole
value=60, cap=40240.0C · Code with teaching comments
Reference implementation previewpublic double fractionalKnapsack(int[] value, int[] weight, int W) { int n = value.length; boolean[] used = new boolean[n]; double total = 0.0; int capacity = W;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The greedy rule itself — 'spend remaining capacity on the highest available value/weight' — is the entire algorithm. The O(n²) here comes only from finding the max by scanning each round; sorting precomputes that order once, which is the single change that makes it fast.
ComplexityO(n²) time, O(1) space — Each round scans all n items to find the best remaining ratio, and there are up to n rounds → O(n²). No sorting and no extra structure → O(1) extra space beyond a used-marker.
E · Edge cases and pitfalls5W = 0 — Loop guard capacity > 0 is false immediately → returns 0.0.Explore edge casesHide edge cases
Edge cases handled
W = 0Loop guard capacity > 0 is false immediately → returns 0.0.all items fitEvery item is taken whole; capacity never forces a fraction, total is the sum of all values.
Pitfalls
- Integer division when computing the ratio — truncates and silently picks the wrong items.
- Sorting by raw value or raw weight instead of the ratio — fails on simple counterexamples.
- Skipping this approach as 'too slow to mention' — verbalising the greedy rule first is what the interviewer grades.
Approach 2 of 2 · Optimal
Sort by Ratio, One Pass (Optimal)
1Hint 1Explore hintHide hint
The baseline keeps re-finding the highest ratio. What if you arranged the items in that order up front?
2Hint 2Explore hintHide hint
Sort items by value/weight descending, then iterate once: take each whole while it fits, and when one doesn't fit, take its fraction and stop.
3Hint 3Explore hintHide hint
Sorting is O(n log n); the fill is O(n). The only state you need is the running total and the remaining capacity.
A · Core idea
Pair each item's value with its weight, sort the pairs by value/weight descending, then sweep once: take each item whole while it fits the remaining capacity; when an item is too big, take exactly the fraction that fills the leftover and stop.
Why sorting replaces the repeated scan. The baseline proved the greedy rule is 'always take the highest available ratio'. But that order never changes as items are consumed — the item with the second-best ratio is still second-best after the best is taken. So instead of re-scanning for the max n times, sort the items by ratio once and the correct order falls out of the array. That turns O(n²) into O(n log n).
Why a single fractional take is enough. Walking in descending-ratio order, you take wholes until the running weight would overflow W. At that exact item, the leftover capacity capacity is less than weight[i], so you take fraction capacity / weight[i], add value[i] · fraction, and you're full. Everything before it was strictly higher (or equal) ratio, everything after is lower — so no rearrangement could beat this.
The exchange argument that proves optimality. Suppose some optimal solution spends capacity on a lower-ratio item while leaving room it could have given to a higher-ratio item. Move one unit of weight from the lower-ratio item to the higher-ratio one: total value strictly increases (you gain more per unit than you lose), and capacity usage is unchanged. So the original wasn't optimal — contradiction. Repeating this argument shows the optimum must fill capacity in descending ratio order, which is exactly what this algorithm does.
Why fractions are load-bearing. This exchange only works because you can move partial weight. In the 0/1 version you can't split, so shifting a unit isn't allowed, the argument breaks, and the problem becomes NP-hard. Always say this contrast aloud.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
value = [60, 100, 120], weight = [10, 20, 30], W = 50Array state
ratio 6
take whole (w10), cap 50→40
240.0C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Sorting is a 'precompute the greedy order once' move. Whenever a baseline repeatedly searches for the current best by a fixed key, sorting by that key collapses the repeated search. The deeper idea is the exchange argument: for a divisible resource, optimal means highest density first, provably.
ComplexityO(n log n) time, O(n) space — Sorting n items dominates at O(n log n). The fill is a single O(n) pass. Pairing values with weights to sort needs O(n) auxiliary space (or sort index array).
E · Edge cases and pitfalls6W ≥ total weight — Every item taken whole; loop ends with capacity > 0 and total = sum of all values.Explore edge casesHide edge cases
Edge cases handled
W ≥ total weightEvery item taken whole; loop ends with capacity > 0 and total = sum of all values.single item, W < its weightFirst (only) item is too big → fractional take W/weight·value.two items, equal ratiosOrder between them doesn't matter; total value is identical either way.
Pitfalls
- Sorting ascending instead of descending — fills with the worst material first.
- Comparing ratios with integer division — truncation reorders items incorrectly.
- Forgetting the fractional take and just stopping when an item doesn't fit — leaves capacity unused and undercounts value.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic double fractionalKnapsack(int[] value, int[] weight, int W) { int n = value.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; i++) { idx[i] = i;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Sorting by value instead of ratio
A high-value but heavy item can crowd out two lighter items that together beat it. value=[100,60,60], weight=[50,10,10], W=20: value-first takes part of the 100 (40 value) but ratio-first takes both 60s for 120. Ratio is the only correct key.
Explore the code comparisonHide the code comparison
Sorting by value instead of ratio
A high-value but heavy item can crowd out two lighter items that together beat it. value=[100,60,60], weight=[50,10,10], W=20: value-first takes part of the 100 (40 value) but ratio-first takes both 60s for 120. Ratio is the only correct key.
Don't write this
items = sorted(zip(value, weight), key=lambda vw: vw[0], reverse=True)Write this instead
items = sorted(zip(value, weight), key=lambda vw: vw[0] / vw[1], reverse=True)2Integer division corrupts the ratio
In Java, value[i] / weight[i] with both ints truncates: 60/10 and 100/20 both round oddly relative to each other, scrambling the sort. Cast to double before dividing.
Explore the code comparisonHide the code comparison
Integer division corrupts the ratio
In Java, value[i] / weight[i] with both ints truncates: 60/10 and 100/20 both round oddly relative to each other, scrambling the sort. Cast to double before dividing.
Don't write this
double ratio = value[i] / weight[i]; // int division, truncatedWrite this instead
double ratio = (double) value[i] / weight[i]; // promote to double first3Dropping the partial item
Stopping as soon as an item doesn't fit wastes the leftover capacity. The boundary item must be taken fractionally to fill the knapsack completely.
Explore the code comparisonHide the code comparison
Dropping the partial item
Stopping as soon as an item doesn't fit wastes the leftover capacity. The boundary item must be taken fractionally to fill the knapsack completely.
Don't write this
for v, w in items:
if w <= capacity:
total += v
capacity -= w
else:
break # leftover capacity wastedWrite this instead
for v, w in items:
if w <= capacity:
total += v
capacity -= w
else:
total += v * (capacity / w) # fill the rest
breakRevise
Carry the pattern into the interview
Pattern to remember
Sort by value/weight ratio descending, take wholes then one fraction
Code pattern to memorize
sort items by value/weight descending
total = 0
for each item:
if item.weight <= capacity:
total += item.value
capacity -= item.weight
else:
total += item.value * (capacity / item.weight)
break
return totalRules to remember
- 1Sort by the ratio value/weight, not by raw value and not by raw weight — both of those lose to ratio on simple counterexamples.
- 2You may take a fraction of exactly one item: the last one that partially fits. Every earlier item is taken whole or skipped.
- 3Stop the moment capacity hits 0 — the partial item is always the final action.
- 4Use floating-point (or rational) math for the fractional value; the answer is generally not an integer.
- 5This greedy is optimal only because fractions are allowed. If items are all-or-nothing, it's 0/1 Knapsack — a DP problem, not greedy.
Use this pattern when
- Items are divisible — you can take any fraction of an item's weight and earn the same fraction of its value
- A single capacity constraint and you want to maximise total value
- Continuous resource allocation: fill a budget/bandwidth/volume with divisible goods
- You can rank items by a per-unit desirability and greedily consume the best first
Choose another pattern when
- Items are indivisible (take all or nothing) → 0/1 Knapsack, solved by DP, not greedy
- Multiple capacity dimensions (weight AND volume) → greedy ratio breaks down
- Value isn't linear in the fraction taken → the ratio argument no longer holds
- You need the actual set of items, not just the max value → still fine, but track choices
Interview takeaway
Fractional Knapsack is the cleanest exchange-argument greedy: per-unit value is the only thing that matters when items split, so always spend remaining capacity on the highest-ratio material left. The single divisibility assumption is the entire difference between an O(n log n) greedy and the NP-hard 0/1 Knapsack — naming that distinction is what interviewers listen for.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical exchange-argument greedy for a divisible resource. Recognise it when items can be split and a single capacity is shared: rank by value-per-unit and consume the densest first. The divisibility assumption is exactly what separates this O(n log n) greedy from the NP-hard 0/1 Knapsack.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- 0/1 KnapsackComing soonItems are indivisible — greedy fails; use DP over capacity, O(n·W).
- Unbounded KnapsackComing soonIndivisible but infinite copies of each item — DP where each item can be reused.
- Maximum Units on a TruckComing soonBoxes with units per box and a truck capacity — same sort-by-density greedy, but counts are integer (no fractions of a box).
- IPO (Maximize Capital)Coming soonPick projects under a capital constraint — greedy with a max-heap on profit among affordable projects.