DSA interview question

Fractional Knapsack

Medium · Algorithms · Topics: greedy, sorting

The problem

A thief (or a cargo planner) has a bag with capacity W and n items, each with a value and a weight. Unlike 0/1 knapsack, any fraction of an item may be taken, with proportional value. What's the maximum total value? Because fractions are allowed, greedy by value per unit weight is optimal. Take the items with the best ratio completely, and fill whatever capacity is left with a fraction of the next best item.

Example: W = 50, items (value, weight) = (60,10), (100,20), (120,30) → 240.00 (take the first two fully and two-thirds of the third).

Function signature

double fractionalKnapsack(int W, vector<pair<int, int>> items);  // items: (value, weight), weight > 0

Test cases

Input `(W, items)`	Output	Explanation
`(50, [(60,10), (100,20), (120,30)])`	`240.00`	60 + 100 + 120 · 20/30
`(50, [(60,10), (100,20)])`	`160.00`	Everything fits
`(10, [(500,30)])`	`166.67`	500 · 10/30
`(5, [(10,2), (10,5)])`	`16.00`	10 + 10 · 3/5
`(0, [(10,1)])`	`0.00`

(Confirm: fractions are allowed; values and weights are positive; answers within 10⁻⁶ are accepted, shown here to 2 decimals.)

How interviewers phrase it

"Given weights and values of N items and a knapsack of capacity W, find the maximum total value; you may break items" (GeeksforGeeks "Fractional Knapsack").

Clarifying questions to ask

Can items be split? (Yes. Otherwise it's the 0/1 knapsack DP.)
What precision is expected?
Can weights be 0? (Assume positive.)

Follow-ups to expect

"Why is greedy by ratio optimal here?"
"Why doesn't it work for 0/1 knapsack?"
"How do you compare ratios without floating point?"
"How many items end up fractional?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview