Fractional Knapsack
A medium Greedy problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Greedy
- Sheets
- 3
- Core for
- 3 roles
- Platform
- GeeksforGeeks
The problem
You are given weights and values of n items and a knapsack with capacity W. You can break items into fractions to maximize the total value in the knapsack. Return the maximum value achievable.
Example 1
- Input
- weights = [10,20,30], values = [60,100,120], W = 50
- Output
- 240.0
- Why
- Take the full items with weight 10 (value 60) and weight 20 (value 100), then 2/3 of the item with weight 30 (value 80). Total = 240.0.
Example 2
- Input
- weights = [5,10,15], values = [50,60,70], W = 20
- Output
- 133.33
- Why
- Take the full items with weight 5 (value 50) and weight 10 (value 60), then 1/3 of the item with weight 15 (value ~23.33). Total = 133.33.
Constraints
- 1 <= n <= 10^5
- 1 <= W <= 10^9
- 1 <= weights[i], values[i] <= 10^4
How to think about it
Updated 2026-09-09Because items can be divided into arbitrarily small fractions, every unit of weight competes directly against every other unit. You should never spend a gram of capacity on lower density when higher density is still available, making unit value the sole arbiter of preference.
Approaches, worst first
Greedy sort by value density
time O(n log n) · space O(n)
Compute value per unit weight for every item and sort descending. Greedily take whole items while capacity allows, and take the necessary fraction of the first item that exceeds remaining capacity. The divisibility eliminates the dynamic programming tradeoffs of 0/1 knapsack.
Quickselect partitioningWrite this one
time O(n) · space O(n)
Instead of sorting all items, partition around the median density to find the heaviest items needed to fill capacity W. Avoids a full sort when only the top density items are required, though standard sort is simpler and typically fast enough.
Where people lose marks · 3
- Integer division when computing value/weight truncates ratios and distorts the sort order. Cross-multiplying `v1 * w2` against `v2 * w1` avoids floating-point inaccuracies.
- Floating point accumulation error when summing partial values; ensure values are cast to double precision before multiplication.
- Failing to break early once the knapsack capacity reaches zero leads to unnecessary processing or negative remaining capacity.
The theory behind it
Greedy — the ground this problem stands on. All Greedy problems
What Greedy is
A greedy algorithm makes the best-looking choice available right now, at every step, without ever looking back or second-guessing its decision. Think of a cashier making change by handing over the largest possible coin first, repeatedly, until the total is reached. Unlike dynamic programming, which saves and compares answers to multiple overlapping paths, a greedy strategy commits to one immediate option and keeps moving forward.
When to reach for it
Reach for greedy when problems ask for minimum jumps, interval scheduling, assigning resources to maximize satisfaction, or finding fractional values. Key signals include sorted orders where greedily taking the next item never hurts future options, or gas station round trips where running balances prove reachability. If you can prove that taking the immediate best choice never leaves you worse off than any alternative, greedy gives the fastest answer.
How the pattern works
Start by sorting the input to bring the most promising candidates to the front. At each position, evaluate your local rule, take the best available piece, and update your running state. The crucial mental step is proving the greedy choice property: demonstrate that picking this immediate winner cannot block a better global solution down the road. If choosing an item now forces you to reconsider past decisions when conditions change later, greedy fails and you must switch to dynamic programming instead.
What each operation costs
| Operation | Time |
|---|---|
| sort elements to enable greedy selection | O(n log n) |
| greedy single-pass scan through sorted input | O(n) |
| greedy choice using a priority queue | O(n log n) |
What usually goes wrong with Greedy
- Applying a greedy choice without proving it yields the global optimum, such as picking the largest coin first for arbitrary denominations where dynamic programming was required.
- Forgetting to sort the input before running the greedy loop, making local decisions on unordered elements that produce invalid answers.
- Picking items based on only one attribute when the optimal decision depends on a ratio or combination of multiple attributes.
Which roles need this problem
Greedy is a core topic for these 3 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 4 more roles, including Site Reliability Engineer, Search Engineer, Quant Developer.
Companies that have asked it
Tags taken from the problem's own GeeksforGeeks page — not a copied list.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Greedy problems
Problem set and role mapping as of .