Classic Greedy

Fractional Knapsack

Unlike 0/1 knapsack, you CAN take fractions of items. Sort by value-per-weight ratio (highest first), take as much as possible of each. Greedy works perfectly here because fractions are allowed.

O(n log n)

O(1)

How It Works

Fractional knapsack allows taking arbitrary fractions of items, and that single relaxation makes greedy exactly optimal. Compute each item's value-per-weight ratio, sort descending, and fill the sack: take all of the best-ratio item, then the next, until the remaining capacity forces a fractional piece of the current item, which tops the sack off precisely. Every unit of capacity is spent at the highest available rate, and divisibility guarantees zero wasted space.

An exchange argument formalizes it: swapping any lower-ratio mass for available higher-ratio mass never decreases value, so the greedy loading cannot be beaten. Sorting costs O(n log n) and the fill is O(n). The contrast with 0/1 knapsack — where indivisibility forces O(nW) DP — is a favorite interview probe about when greedy is trustworthy.

Step-by-Step Visualization

Items: (wt=10,v=60), (wt=20,v=100), (wt=30,v=120). Cap=50

100

120

Ratios6, 5, 4 (value/weight)

1/3

Code

Java

static double fractionalKnapsack(int[][] items, int capacity) {
  Arrays.sort(items, (a, b) -> Double.compare((double)b[1]/b[0], (double)a[1]/a[0]));
  double totalValue = 0;

  for (int[] item : items) {
    if (capacity >= item[0]) {
      totalValue += item[1];
      capacity -= item[0];
    } else {
      totalValue += ((double)capacity / item[0]) * item[1];
      break;
    }
  }
  return totalValue;
}

Tips & Gotchas

1Sort items by value-per-weight ratio (descending)

2Take as much of each item as possible, starting with highest ratio

3Only the last item might be partially taken

Practice Problems

1Fractional Knapsack
2Maximum Units on a Truck
3Bag of Tokens
4Maximum Bags With Full Capacity of Rocks

About the Classic Greedy Pattern

Standard problems where the greedy approach has an elegant proof of correctness.

Key insight

Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.

Common Greedy Interview Problems

Jump Game
Activity Selection
Meeting Rooms II
Gas Station
Candy
Task Scheduler
Partition Labels

Frequently Asked Questions

Why does greedy fail for 0/1 knapsack but succeed here?

With indivisible items, the best-ratio item can consume capacity awkwardly and block a better combination — ratios alone cannot capture packing interactions. Divisibility removes that: leftover capacity is always filled exactly by a fraction, so per-unit value is the only thing that matters.

How is Maximum Units on a Truck an instance of this pattern?

Each box type is effectively divisible cargo because you can load any number of boxes up to the count available, and each box of a type has identical per-box value. Sorting by units per box and loading greedily is fractional knapsack with integer granularity that happens to fit.

What edge cases deserve care in an implementation?

Zero-weight items with positive value should be taken outright before ratios are computed to avoid division by zero. Also confirm whether the answer wants total value (possibly fractional) or a description of the load, and use exact arithmetic or careful floating-point comparison when ratios tie.