Part-loads of loose tea

A courier has a flatbed with a weight limit and an auction floor full of loose tea. Tea pours, so a lot too big to fit whole can still be part-loaded.

The problem

Each lot is a pair [kilos, value]: what the whole lot weighs and what it is worth. The tea is loose, so any amount may be scooped out — t kilograms of a lot weighing kilos and worth value fetch value * t / kilos.

The flatbed carries capacity kilograms. Load it so the value on board is as large as possible.

Input. lots — a list of [kilos, value] pairs. capacity — the flatbed limit in kilograms.

Output. The greatest value that fits, rounded to five decimal places.

Example.

lots = [[9, 54], [5, 45], [12, 60], [7, 28]], capacity = 15   ->  104.0

Per kilogram the lots are worth 6, 9, 5 and 4: the 5 kg lot goes on whole for 45, the 9 kg lot for 54, and one kilogram of the 12 kg lot adds 5.

A second example, where sealing the lots would change the answer:

lots = [[3, 10], [4, 20]], capacity = 5   ->  23.33333

The 4 kg lot pays 5 a kilogram and goes on whole; one kilogram of the other follows at 10/3. Sealed chests would cap the load at the 4 kg chest alone, worth 20 — same sort, different answer.

Constraints.

• 1 <= len(lots) <= 10^5
• 1 <= kilos <= 10^4
• 1 <= value <= 10^6
• 0 <= capacity <= 10^9

Hints

Approach

Brute force

Choose a subset to take whole, then top up from one more lot: 2ⁿ subsets before the top-up is even considered.

The insight

Sort the lots by value per kilogram and take them whole down the list; the only lot ever split is the one that runs out of room.

Suppose a load carries a kilogram of lot B while a denser lot A sits on the floor. Swap them: the weight is unchanged and the value rises, so that load was not optimal. An optimal load takes all of a denser lot before any of a thinner one, which is the sorted order. The precondition is divisibility — the swap must be legal one kilogram at a time. Sealed lots remove it, and no sort is then enough.

Algorithm

1. Sort the lots by value / kilos, largest first.
2. Hold room = capacity and total = 0.
3. For each lot in turn: if kilos <= room, load it whole, add value, and subtract kilos from room.
4. Otherwise load room kilograms for room * value / kilos and stop — the flatbed is full.
5. Return total, rounded to five decimal places.

Complexity

Time O(n log n) — the sort dominates; the load is one pass. Space O(n) for the sorted order, O(1) beyond it.

Solution

"""Part-loads of loose tea — fractional knapsack by value density."""


def solve(lots, capacity):
    room = capacity
    total = 0.0
    # densest first: an optimal load never carries a thinner kilogram while a
    # denser one is still on the floor, because swapping them raises the value
    for kilos, value in sorted(lots, key=lambda lot: lot[1] / lot[0], reverse=True):
        if room == 0:
            break
        if kilos <= room:
            total += value
            room -= kilos
        else:
            total += room * value / kilos  # the one split lot fills the bed
            room = 0
    return round(total, 5)

TESTS = [
    (([[9, 54], [5, 45], [12, 60], [7, 28]], 15), 104.0),
    (([[3, 10], [4, 20]], 5), 23.33333),
    (([[2, 7], [1, 3]], 2), 7.0),
    (([[4, 20], [6, 30]], 100), 50.0),
    (([[4, 20]], 0), 0.0),
    (([[5, 45], [9, 54], [12, 60], [7, 28]], 7), 57.0),
]

Pitfalls

• Sorting by value. A 10,000 kg lot worth 100 outranks a 1 kg lot worth 90 while paying a nine-hundredth as much per kilogram; the flatbed fills with cheap tea.
• Computing the density with integer division. On [[2, 7], [1, 3]] with a 2 kg limit, 7 // 2 and 3 // 1 are both 3, so the 1 kg lot may sort first and the load comes to 6.5 instead of 7.
• Using this sort on sealed lots. It reports 23.33333 for the second example when the true best is 20 — an answer that is not just wrong but unreachable.
• Ignoring a zero capacity. Nothing is loaded, and the answer is 0.0, not the first lot's value.

Variants

• The single enlarger — another swap argument, where a booking is exchanged rather than a kilogram.
• The exchange argument — the divisibility precondition, and what replaces greedy without it.