---
title: "Fractional Knapsack"
description: "When items can be split, packing by value density is optimal"
source: https://vizlearn.app/algorithms/greedy/fractional-knapsack
access: premium (interactive player requires Lifetime; this doc is free)
---

# Fractional Knapsack

Fractional knapsack is the greedy packing problem where items can be split: sort items by value density (value ÷ weight), load whole items from the densest down, and cut the first item that doesn't fit to fill the capacity exactly. Because fractions are allowed, this greedy fill is provably optimal — and once splitting is forbidden, the same rule stops being safe.

There is a picture that makes the whole algorithm obvious. Draw each item as a rectangle: width = weight, height = value density. Then area = value, and the knapsack is a shelf of fixed total width. Packing greedily by density means putting the tallest rectangles on the shelf first, and cutting the last one vertically — the slice keeps its full height, so every unit of shelf width earns as much as it possibly can. That geometric picture is the heart of the optimality proof; the exchange argument below makes it precise.

## How Fractional Knapsack Works

Compute each item's density, `value / weight` — what one unit of capacity earns if spent on that item. Sort the items by density, highest first. Then fill: while the next item fits whole, take all of it; when an item is wider than the remaining gap, take `min(weight, remaining)` — a fraction — and the knapsack is exactly full. Any items after the cut are never touched.

The model assumes items are independent and continuously divisible with constant value per unit — the shape of allocating a budget, bandwidth, or cargo hold across divisible resources. The moment a resource has diminishing returns or all-or-nothing chunks, the rectangles lie, and you're in a different problem.

## Why Splitting Makes Greedy Safe — and Why 0/1 Breaks It

An exchange argument in one sentence: if a filled knapsack carries any weight at density d while some unloaded item still offers density d′ > d, swap a sliver of the cheap weight for a sliver of the dense item and the total value rises. Divisibility is what makes the swap always available — you never have to move a whole item, just a sliver. So the only fill that cannot be improved is the one that spends every unit of capacity at the highest available density: the greedy fill. The animation stages this swap right after the sort — a sliver of the lowest-density item is placed on the shelf, then replaced by an equally wide sliver of the highest-density one, and the extra area over the same width is the gain.

That argument leans on splitting at both ends of the swap, which is exactly why it dies in the 0/1 world. When items are indivisible, the greedy rule can strand capacity — a dense-but-wide item may not fit at all, and nothing fills the hole. The animation's second act stages this failure on the default input: forbid the cut, replay the same rule, and watch it land below even the best whole-item packing. That gap is the entire reason the 0/1 knapsack needs dynamic programming.

## Fractional Knapsack Step by Step

The default input is capacity 50 with four items, given as `value/weight`: A = 120/30, B = 60/10, C = 45/15, D = 100/20.

1. **Densities.** A: 120 ÷ 30 = 4.0. B: 60 ÷ 10 = 6.0. C: 45 ÷ 15 = 3.0. D: 100 ÷ 20 = 5.0. Note that A, the most *valuable* item, is only third by density.
2. **Sort.** Density order: B (6.0), D (5.0), A (4.0), C (3.0).
3. **The exchange check.** Before filling, the animation stages the greedy bet: put 10 shelf units of C (density 3.0) on the empty shelf — worth 30 — then swap the same width to B (density 6.0). The rectangle is taller over the same width, and the extra area is the gain: 10 × (6.0 − 3.0) = 30. Any width spent below the best available density can be upgraded this way, which is exactly why the fill goes densest-first.
4. **Take B whole.** Weight 10 ≤ remaining 50. Value 60, remaining 40.
5. **Take D whole.** Weight 20 ≤ remaining 40. Value 160, remaining 20.
6. **Cut A.** Weight 30 > remaining 20, so take = min(30, 20) = 20 — two thirds of A. That earns 120 × 20/30 = 80. Value 240, remaining 0.
7. **Stop.** The knapsack is full; C is never considered. Total: **240**.
8. **Now forbid splitting.** The slice pops back out, and A — whole-or-nothing now — is rejected outright: its weight 30 exceeds the 20-unit gap that B and D leave. The scan continues with whole items only, C loads, and the total settles at **205**.
9. **Compare with the true 0/1 optimum.** Exhaustive check of all 16 whole-item packings: A + D weighs exactly 50 and is worth **220**. So the no-split greedy (205) isn't even 0/1-optimal, and both lose to fractional greedy (240). One cut was worth 35.

In the animation, watch the cut beat: the red line lands exactly where the remaining-capacity bracket ends, and the slice that slides onto the shelf is *just as tall* as the bar it came from. Height is density; the fraction costs you nothing per unit. The final beat draws the three totals — 205, 220, 240 — as proportional bars.

## Time and Space Complexity

| Phase | Cost |
| --- | --- |
| Computing densities | O(n) |
| Sorting by density | O(n log n) |
| The fill scan | O(n) |

Total: **O(n log n)** time, dominated by the sort, and O(1) auxiliary space beyond the sorted order. There is no interesting worst case — every input costs one sort and one scan. Contrast with 0/1 knapsack, where the classic exact algorithm is O(n·W) dynamic programming — pseudo-polynomial, and no polynomial-time exact algorithm is known; divisibility is what collapses an NP-hard problem into a sort.

## Edge Cases

- **Everything fits.** If total weight ≤ capacity, every item loads whole, the cut never fires, and greedy is trivially optimal — the fractional, no-split, and 0/1-optimal totals all agree. The "All items fit" scenario shows this: divisibility bought nothing, because nothing needed dividing.
- **The first item is already too wide.** With capacity below the densest item's weight, the very first pick is a fraction and the scan ends immediately. The "First item cut" scenario takes 20 of a 30-weight item and never looks at the rest.
- **An exact fit.** When an item's weight equals the remaining capacity exactly, it loads *whole* — `min(weight, remaining) = weight` — and no cut happens. A trace that renders a "cut" on an exact fit is lying about the arithmetic.
- **Equal densities.** When items tie, order between them doesn't matter: any tie-break gives the same total (this lesson breaks ties by input order for reproducibility). The "Equal densities" scenario makes the indifference visible.
- **Fractional totals.** The default input is chosen so every number is exact (2/3 of 120 is 80), but a custom input like 20 of 100/30 yields repeating decimals; the display rounds to one decimal place.

## Common Mistakes

- **Sorting by value instead of density.** A big price tag can hog capacity at a poor rate. On the default input, value order would pick A (120) first, spending 30 of 50 capacity at density 4.0 while B's density 6.0 waits — the fill ends at 220, not 240. Only value *per weight unit* says what each unit of capacity earns.
- **Carrying the rule into 0/1 knapsack.** Density-greedy without splitting is not optimal — the animation's own contrast act ends at 205 against an optimum of 220. When items are indivisible, take-it-or-leave-it interactions between weights matter, and that is dynamic programming's job, not a sort's.
- **Charging the full value for a partial item.** The slice earns `value × take/weight`, not `value`. Geometrically: you kept the height but only part of the width, so you only earned part of the area.
- **Continuing the scan after the knapsack is full.** Once remaining capacity hits zero the loop must stop; "topping up" later items past the first cut would exceed capacity. One cut, at most, ever happens.
- **Comparing densities with floats carelessly.** `value / weight` ties can wobble under floating point. Cross-multiplying (`v1 × w2` vs `v2 × w1`) keeps the sort exact — it's how this lesson's trace stays deterministic.