skip to content

Sorting cargo by value per tonne is optimal for divisible grain but wrong for indivisible crates - why?

level: middleimportance: must knowfreq 66%

answer

  1. One word in the statement changes everything
  2. Ask whether the last unit of capacity can be topped up
  3. Try to swap a tonne between two loads
  4. Whole crates can strand unusable capacity
  5. Stranded capacity carries value zero

basics

~20 s

Divisible cargo lets you fill the last sliver of capacity with the best remaining density, so no swap can improve the load and greedy is provably optimal. Indivisible crates can strand capacity, so a lower-density crate may pay more.

solid answer

~50 s

For divisible cargo, sorting by value per tonne and pouring greedily is provably optimal: every tonne of capacity ends up carrying the highest density still available, so no exchange of loaded for unloaded cargo can raise the total. That is an exchange argument, and it is the whole proof. Indivisibility removes it. Take a 10-tonne hold, crate A at 6 t worth 12 (density 2.0) and crate B at 10 t worth 19 (density 1.9). Density-greedy loads A, leaves 4 t of capacity that nothing fits into, and ships value 12; loading B alone ships 19. The greedy step was locally best per tonne and globally wrong because the capacity it stranded had no value. Divisible cargo is a sorting problem, `O(n log n)`; the indivisible version needs an exact method whose cost scales with the capacity as well as the crate count.

code

pseudocode · 13 lines
pseudocode
// items sorted so that value[i]/weight[i] is descending
total = 0
space = capacity
for i in 0..n-1
    if weight[i] <= space
        total = total + value[i]
        space = space - weight[i]
    else
        // load only the fraction that fits
        total = total + value[i] * (space / weight[i])
        space = 0
        break
// delete the else branch and the same loop is only a heuristic

go deeper

for a junior

Know that whether items can be split is the question to ask first. Splitting allowed means sort by value per unit weight and pour; whole items only means that rule is a guess, not an algorithm.

for a middle

Be able to state the exchange argument in two sentences and to invent a two-item counterexample for the whole-item case on the spot. Recalling the verdict without the counterexample is the weaker answer.

for a senior

Point out the cost consequence: the divisible version is sort-dominated, while the exact whole-item version scales with capacity as well as item count, which can be the difference between shipping and not shipping.

for a principal

Frame divisibility as a modelling choice the business sometimes controls. Repacking, splitting shipments or standardising crate sizes can convert a hard optimisation into a provable sort - a design lever worth raising before an algorithmic one.

## Two problems that look identical Both versions read the same on the whiteboard: a hold of fixed capacity, a set of cargo items each with a weight and a value, maximise the value shipped. One word separates them. If the cargo is divisible - grain, fuel, aggregate - you may load any fraction of an item. If it is indivisible - sealed crates, containers, machines - each item is taken whole or left behind. That single word changes which algorithmic paradigm is correct, and interviewers flip it deliberately to see whether you noticed. ## Why greedy is provably optimal when cargo divides Sort items by value density, value divided by weight, highest first. Load them in that order, and when the next item does not fit whole, load exactly the fraction that fills the remaining space. The proof is an exchange argument. Consider any optimal load and compare it with the greedy load. If they differ, the optimal load must be carrying some tonne of a lower-density item while a tonne of a higher-density item was left behind - otherwise it *is* the greedy load. Swap that tonne for a tonne of the higher-density item. The weight is unchanged, so the load is still legal, and the value did not fall. Repeat the swap; each one moves the optimal solution one step closer to the greedy one without ever losing value. Therefore the greedy load is optimal too. The swap is only legal because you can move *a tonne* rather than a whole item. Divisibility is not a convenience here; it is the hinge of the entire proof. ## The two-crate counterexample when cargo does not divide Hold capacity: 10 tonnes. | Crate | Weight | Value | Density | |---|---|---|---| | A | 6 t | 12 | 2.00 | | B | 10 t | 19 | 1.90 | Density-greedy takes A first (2.00 beats 1.90). That leaves 4 tonnes of capacity, and B needs 10, so B is left on the dock. Shipped value: **12**. The optimum is to ship B alone: **19**. Greedy is off by more than 50%, on two crates. Run the same numbers with divisible cargo and greedy shines: all of A (12) plus 4 tonnes of B (4 x 1.9 = 7.6) gives 19.6, beating every whole-crate load. The same rule is exactly optimal in one world and badly wrong in the other. ## What actually broke The greedy-choice property is the claim that the locally best move belongs to some optimal solution. For divisible cargo it holds: some optimal load contains as much of the densest item as fits. For indivisible cargo it does not, because taking the densest crate can strand capacity, and stranded capacity carries value zero. Density measures value *per tonne carried*, and the crate's real cost includes the tonnes it wastes - a quantity density cannot see. Note also what does *not* rescue the greedy: sorting by raw value instead of density fails just as readily (a hold of 10 with one 10-tonne crate worth 20 and two 5-tonne crates worth 15 each ships 20 instead of 30). No single sort key is correct, which is the point - the problem is not a sorting problem. ## The cost you pay for indivisibility The divisible version is dominated by the sort: `O(n log n)`, or linear with a selection-based pivot on density. It needs no table and no capacity-sized memory. The indivisible version is a genuinely harder problem - its decision form is NP-hard. The standard exact method's cost grows with the number of crates *multiplied by the capacity*, so it is fast for a 10-tonne hold measured in tonnes and infeasible for a hold measured in grams. That is why the divisible-versus-indivisible distinction is not academic: it is the difference between a sort and a capacity-scaled computation. If an approximate answer is acceptable for the indivisible case there is a cheap fallback worth knowing: take the better of the density-greedy prefix and the single most valuable crate that fits. That combination is guaranteed to reach at least half the optimum, and on the counterexample above it reports 19, the true optimum, because the single-crate branch catches B. ## How to use this in an interview When a packing-style problem appears, your first question should be whether items split. If they do, say so, name the density sort, and give the exchange argument - it is short, and stating it distinguishes you from candidates who merely remember the rule. If they do not, say that density-greedy is a heuristic here, produce a two-item counterexample on the spot, and move to an exact formulation. Producing the counterexample from scratch is the strongest signal in this whole area: it shows you can test the greedy-choice property rather than recall a verdict about it.

  • Does sorting by raw value instead of density fix the indivisible case?
    No. With a 10-tonne hold, one 10-tonne crate worth 20 and two 5-tonne crates worth 15 each, value-first ships the single crate for 20 while the pair ships 30. No fixed sort key is correct for indivisible cargo, because the right choice depends on how the remaining capacity gets used, which a per-item key cannot express.
  • If you must answer fast on the indivisible version, can you bound how wrong greedy is?
    Yes. Take the better of two candidates: the density-greedy prefix, and the single most valuable crate that fits on its own. That pair is guaranteed to reach at least half the optimum, and it costs only the sort. On the two-crate counterexample the single-crate branch reports 19, which happens to be exactly optimal. Say this when the interviewer adds a latency constraint.
  • Where exactly does the exchange argument break once crates cannot be split?
    The argument swaps a unit of weight from a lower-density item for a unit from a higher-density one, keeping the load legal because weight is unchanged. With whole crates you cannot move one tonne - you must move a whole crate, which changes the weight and can make the load illegal or leave capacity unused. The swap that drove the proof is no longer available.

Pouring liquids into a jug versus stacking boxes in it: liquids always fill to the brim, boxes leave gaps you cannot pour into.

saying these in an interview costs you the question

  • Says sorting by value density solves both versions
  • Treats splitting items as an unimportant detail
  • Believes some other sort key rescues the whole-item case
  • Cannot construct a counterexample and only recalls the verdict
  • Assumes the highest-density item is always in the optimal load

context

resolving links…