On this page
Description
A knapsack holds a fixed weight, and items can be cut - flour, fuel, bandwidth, a budget. Which items, and how much of each, give the most value? Because any fraction is allowed, one simple ordering answers it exactly.
It is the only knapsack variant a greedy solves. This skill covers the density sort, why only one item is ever split, how to compare densities without rounding, and why the same idea fails the moment items can't be cut. That failure is also what makes the fractional answer useful as a bound for the harder problem.
We'll go from simple to more technical:
- The pattern: sort by value per unit of weight, take whole items, then a fraction of the next.
- A second flavor: items that can't be split, where the greedy stops being optimal.
- Where divisible budgets show up (ad spend, bandwidth, blending materials).
- What breaks it: sorting by value, integer density, overflow, indivisible items.
The approach
Java
double maxValue(int[] values, int[] weights, int capacity) {
Integer[] order = new Integer[values.length];
for (int i = 0; i < order.length; i++) order[i] = i;
// highest value per unit of weight first; cross-multiply in long instead of dividing
Arrays.sort(order, (a, b) -> Long.compare((long) values[b] * weights[a], (long) values[a] * weights[b]));
double total = 0;
int remaining = capacity;
for (int i : order) {
if (remaining == 0) break;
int take = Math.min(weights[i], remaining); // all of it, or what still fits
total += (double) values[i] * take / weights[i];
remaining -= take;
}
return total;
}
Python
from fractions import Fraction
def max_value(values: list[int], weights: list[int], capacity: int) -> float:
items = sorted(zip(values, weights), key=lambda item: Fraction(item[0], item[1]), reverse=True)
total = 0.0 # highest value per unit of weight first, ranked exactly
remaining = capacity
for v, w in items:
if remaining == 0:
break
take = min(w, remaining) # all of it, or what still fits
total += v * take / w
remaining -= take
return total
Every unit of capacity should go to whatever earns the most per unit, so sort by density (value / weight), not by value: with items (60, 10), (100, 20), (120, 30) and capacity 50, density order takes 60 + 100 + two-thirds of 120 = 240, while value order takes 120 + 100 = 220. Only the last item taken is ever split. Comparing densities by cross-multiplying avoids two traps: integer division makes 5/3 and 7/4 both equal 1, and the products (up to 10^5 x 10^5) overflow an int, so they're computed in long.
A second flavor: when items can't be split
In 0/1 knapsack each item is taken whole or not at all, and density order stops being optimal. The same three items: density greedy takes (60, 10) and (100, 20) for 160, and then (120, 30) no longer fits - but (100, 20) + (120, 30) = 220. Leftover capacity can't be filled with a fraction, so an early "good deal" can block a better combination. 0/1 knapsack needs dynamic programming (see 0/1 Knapsack).
The fractional answer is still useful there: it's an upper bound on the 0/1 optimum, because relaxing the rules can't lower the best value. Branch-and-bound solvers use exactly that bound to prune.
Where you'll see it
Splitting a divisible budget across options with a constant return per unit (ad spend, bandwidth, storage tiers), and blending raw materials by value per kilogram, use density order - as long as returns really are linear. When each unit earns less than the one before (diminishing returns), the greedy has to re-rank as it goes.
Which tool for which job?
| You need | Use |
|---|---|
| Most value, items can be cut | sort by density, fill, split the last item |
| Most value, items whole or nothing | 0/1 knapsack DP |
| A quick upper bound for 0/1 knapsack | the fractional answer |
| Unlimited copies of each item, whole only | unbounded knapsack DP |
| Returns that shrink with each unit | re-rank as you go (a heap of marginal gains) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Sorting by value | heavy items crowd out denser ones (220 instead of 240) | sort by value / weight |
Integer density, v / w in int | 5/3 and 7/4 tie at 1; 5.25 drops to 5.00 | cross-multiply, or Fraction in Python |
| Cross-products in int | v1 * w2 can reach 10^10 and overflow | compute them in long |
| Using it for indivisible items | a dense, awkward item blocks a better pair (160 instead of 220) | 0/1 knapsack DP |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why sort by value / weight instead of by value?
Show answer
Capacity is the limited resource, so each unit should earn as much as possible. A valuable but heavy item can earn less per unit than lighter items - with (60, 10), (100, 20), (120, 30) and capacity 50, value order gets 220 and density order 240.
2. Why does density greedy fail when items can't be split?
Show answer
Leftover capacity can no longer be filled with a fraction, so taking a dense but awkwardly sized item can block a better combination: the example gets 160 by density instead of 220. 0/1 knapsack needs DP.
3. Why compare (long) v1 * w2 with (long) v2 * w1 instead of v1 / w1 with v2 / w2?
Show answer
Integer division truncates (5/3 and 7/4 both become 1) and loses the ranking, and floating-point division can round. Cross-multiplying compares the fractions exactly; long avoids overflow, since each product can reach 10^10.
Key takeaways
- Divisible items: sort by density, take whole items, then a fraction of the first that doesn't fit.
- At most one item is split.
- Compare densities by cross-multiplying in long - no integer division.
- Indivisible items (0/1 knapsack) need DP; the fractional answer is only an upper bound.