GreedyAlgorithmaka continuous knapsack, value-density greedy

Fractional Knapsack

Maximize value in a capacity-limited knapsack when items can be taken in fractions: take items in decreasing value-per-weight order.

Pattern: GreedyPractice (2)
Progress

Overview

Given items with weight w_i and value v_i and a knapsack of capacity W, choose amounts x_i ∈ [0, 1] maximizing Σ v_i x_i subject to Σ w_i x_i ≤ W. Because fractions are allowed, the greedy rule highest value density `v_i / w_i` first is optimal: fill with the densest item entirely, then the next, and put a fraction of the first item that does not fit.

This is the clearest contrast between greedy and Dynamic Programming: allowing fractions makes the exchange argument go through; forbidding them (0/1 Knapsack) breaks it, and the problem becomes NP-hard in general (pseudo-polynomial DP in O(nW)).

greedyknapsackvalue densityexchange argumentsorting

Intuition

A mental model before the formal terms.

Think of the items as piles of gold dust, silver dust, and sand. You have one bag. Obviously you scoop the gold first — every gram of bag space filled with gold is worth more than the same gram filled with anything else. Fill until the bag is full, and the last scoop may be a partial one.

The reason 0/1 breaks this: if the gold comes as a single bar heavier than the bag, you cannot take part of it, and a mix of lighter, less dense items may be worth more than what fits.

How it works

  1. Compute density v_i / w_i for each item and sort descending.
  2. For each item in that order: if w_i ≤ remaining, take it all (x_i = 1, remaining −= w_i, value += v_i).
  3. Otherwise take the fraction x_i = remaining / w_i, add v_i · x_i, and stop — the knapsack is full.
  4. Optionally use Quickselect on densities to find the break item in O(n) instead of sorting.

Why it works

Exchange argument. Let G be the greedy solution and O any feasible solution that differs from it. Let i be the densest item where O takes less than G (x_i^O < x_i^G). Since O is feasible and uses the capacity G gives to i on some less dense item j (density d_j ≤ d_i), move a small weight ε from j to i in O: value changes by ε(d_i − d_j) ≥ 0. Repeating never decreases value and turns O into G, so value(G) ≥ value(O).

The argument requires divisibility: moving weight ε between items must be allowed. With 0/1 constraints you cannot move ε of an item, so the exchange fails — which is exactly why 0/1 knapsack has no greedy solution.

Only the last item taken is fractional: all denser items are taken whole and the greedy stops when capacity is exhausted.

Recognition

How to tell a problem wants this.

  • Items are divisible ("liquids", "grains", "you may take part of an item", "continuous").
  • A single linear capacity constraint and a linear objective — this is a one-constraint linear program, and LPs with one constraint are solved greedily.
  • If the problem says each item is taken whole or not at all, stop: it is 0/1 Knapsack.
“maximum number of non-overlapping” → Greedy

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1sort items by v/w descending
2remaining = W; value = 0
3for (v, w) in items:
4  if w <= remaining: value += v; remaining -= w
5  else: value += v * remaining / w; break
6return value

Implementations

1from typing import NamedTuple
2 
3# Fractional knapsack: unlike 0/1 knapsack, items can be split. That single
4# relaxation turns an NP-hard problem into a sort — take items in decreasing
5# value-per-weight order and split whatever is left at the boundary.
6 
7 
8class Item(NamedTuple):
9    value: float
10    weight: float
11 
12 
131 · Sort by density (value per unit weight), highest first
14def max_value(items: list[Item], capacity: float) -> float:
15    ordered = sorted(items, key=lambda it: it.value / it.weight, reverse=True)
16 
17    total = 0.0
18    left = capacity
19    for it in ordered:
20        if left <= 0:
21            break
222 · Take the whole item if it fits, otherwise the fraction that does
23        if it.weight <= left:
24            total += it.value
25            left -= it.weight
26        else:
27            total += it.value * (left / it.weight)
28            left = 0
29    return total
30 
31 
323 · The exchange argument: if an optimal solution takes any amount of a
33# lower-density item while a higher-density one is not fully taken, swapping
34# a unit of weight between them strictly increases the value. So no optimal
35# solution can skip density order — and at most ONE item is ever split.
36def count_split_items(items: list[Item], capacity: float) -> int:
37    ordered = sorted(items, key=lambda it: it.value / it.weight, reverse=True)
38    split = 0
39    left = capacity
40    for it in ordered:
41        if left <= 0:
42            break
43        if it.weight > left:
44            split += 1
45        left -= min(it.weight, left)
46    return split  # always 0 or 1
47 
48 
494 · The same greedy is WRONG for 0/1 knapsack, where items cannot split:
50# items (v=6,w=3),(v=5,w=2),(v=4,w=2) with capacity 4 — density order takes
51# the first (density 2) for value 6, but 5+4=9 is optimal
52def knapsack_01(value: list[int], weight: list[int], capacity: int) -> int:
53    dp = [0] * (capacity + 1)
54    for v, w in zip(value, weight):
555 · Iterate capacity downward so each item is used at most once
56        for c in range(capacity, w - 1, -1):
57            if dp[c - w] + v > dp[c]:
58                dp[c] = dp[c - w] + v
59    return dp[capacity]
Walkthrough
  1. key=lambda it: it.value / it.weight, reverse=True is the direct expression of "sort by density, highest first" — Python's key-based sort makes the cross-multiplication trick unnecessary for readability, though it does perform a division per element.
  2. Because the key is computed once per element (not once per comparison), the division cost is O(n) rather than O(n log n) — which is why Python can afford the readable form where C++ prefers cross-multiplication.
  3. total = 0.0 rather than 0 keeps the accumulator a float from the start, which matters if the caller inspects the type.
  4. for v, w in zip(value, weight) pairs the two parallel lists, and zip stops at the shorter one — silently, which is worth knowing.
  5. range(capacity, w - 1, -1) is the downward iteration that keeps each item single-use.
Complexity (this implementation)
time O(n log n) for the fractional version; O(n * capacity) for the 0/1 DP · space O(n) for the sorted copy; O(capacity) for the DP

The key-based sort evaluates the density once per item, so the readable division-based key costs no more than cross-multiplication.

Language notes
  • sorted(key=..., reverse=True) computes the key once per element, which is why the natural value / weight expression is not a performance problem here.
  • zip truncates to the shorter iterable without warning; zip(..., strict=True) (Python 3.10+) raises instead.
  • A zero weight would raise ZeroDivisionError in the key — a precondition worth asserting.
  • fractions.Fraction gives exact density comparison for integer inputs if float rounding ever matters.
Common mistakes in this language
  • Passing an item with zero weight, which raises ZeroDivisionError inside the sort key.
  • Using zip on mismatched lists and silently dropping the tail.
  • Iterating the DP capacity upward.
Language differences that matter here
  • Sort key versus comparator changes the right implementation: Python computes the density once per element via key=, so the readable division is free, while C++ and JS/TS call a comparator O(n log n) times and prefer cross-multiplication.
  • Descending order is a reverse=True flag in Python and a flipped comparator in C++ and JS/TS — where flipping the operands wrongly is an easy and silent mistake.
  • Zero weight fails differently: ZeroDivisionError in the Python key, and a silent infinity or NaN in the other three.
  • Exact density comparison for integer inputs is available in Python (fractions.Fraction) and via cross-multiplication elsewhere; only Python has an exact rational type in the standard library.

Complexity

Best
—
Average
O(n log n)
Worst
O(n log n)
Space
O(1)

Sorting dominates. O(n) expected with quickselect on the density to locate the break item.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Divisible resources under one linear capacity: budget allocation across continuous investments, bandwidth, fuel.
  • As an upper bound (LP relaxation) for branch-and-bound on the 0/1 knapsack.
Avoid it when
  • 0/1 knapsack: capacity 50, items (value 60, weight 10), (100, 20), (120, 30). Densities 6, 5, 4. Greedy takes the first two (weight 30, value 160) and cannot fit the third; optimum is items 2 + 3 (weight 50, value 220). Use 0/1 Knapsack DP.
  • Multiple capacity constraints (weight and volume) — a multi-dimensional knapsack; density is not well defined.
  • Items with a minimum take amount or fixed setup cost — the objective is no longer linear.

Alternatives

0/1 KnapsackUnbounded KnapsackQuickselect

Common mistakes

  • Sorting by value alone or by weight alone instead of by ratio.
  • Forgetting to break after the fractional item — subsequent items would be added with remaining = 0 only if the loop is written carefully; explicit break is clearer.
  • Applying the greedy to a problem that says "cannot break an item".
  • Integer division when computing the density.

Interview patterns

  • Explain why the greedy proof needs divisibility, then contrast with the 0/1 counterexample — this pair is the classic "greedy vs DP" question.
  • LP-relaxation bound in branch-and-bound for 0/1 knapsack.
  • Variants: maximize units of value per time (fill a truck, schedule CPU), same density rule.
Interview questions on this
Mock interviews

Example problems

Partition Equal Subset SummediumFractional Knapsackeasy