Practice: Loading a Van by Value per Kilo

Parcels can be split for loose goods but not for boxed ones, and the greedy rule works for only one of them.

Loading a van by value per kilo practises choosing a greedy key and then testing it with a counterexample: the van carries 5 kilos and there are three loads to choose from. Work it on paper before opening the answer.

The loads are A, 1 kilo worth £6; B, 5 kilos worth £25; and C, 4 kilos worth £16. The goal is the most value in the van.

Choose a sort key for a greedy rule, and say why.
The loads are loose goods, such as flour or coffee beans, so any part of a load can be taken, worth its share of the value. Apply the rule. What value does it carry?
Now the loads are sealed boxes that must go whole or not at all. Apply the same rule. Is its answer the best? If not, give the best load.

Show the answer

Sort by value per kilo, highest first, because each kilo of room should carry as much value as it can. A is worth £6 a kilo, B £5 and C £4. Sorting by value alone takes B first and carries £25 of loose goods; sorting by weight takes A then C and carries £22.
Take all of A, 1 kilo, then fill the remaining 4 kilos from B, worth 4/5 of £25 = £20, for £26. An exchange argument proves it: any load holding a kilo of something worth less per kilo can swap that kilo for one worth more and gain.
The same rule takes A, then cannot fit B in the 4 kilos left, so takes C, for £22. That is not the best: B alone fills the van for £25. The exchange argument fails here because a box cannot be swapped a kilo at a time. A run checked all three answers, the last against every subset of boxes:

The three loads, and what each version of the problem takes
Load	Kilos	Value	Value per kilo	Taken when divisible	Taken when whole
A	1	£6	£6	All of it	No
B	5	£25	£5	4 kilos	Yes
C	4	£16	£4	None	No

The divisible version is the fractional knapsack problem, and the greedy rule solves it in the time of a sort, O(n log n). The whole version is the 0/1 knapsack problem: no sort key solves it, because taking the best load per kilo can leave room that nothing else fits. Knapsack and Grid Dynamic Programming, a later topic, solves it with a table.

← → move through sections and cards