807. The Best Ratio of k Items
A buyer is choosing exactly k items out of n. Item i is worth a[i] and weighs
b[i]. The buyer wants the best value per kilogram OVERALL, that is the largest
(a of the chosen items, added up) / (b of the chosen items, added up)
Print that largest ratio, to exactly 6 digits after the decimal point.
items (5,1) (3,1) (1,1) (2,1), k = 2 -> 4.000000
items (1,1) (2,3) (3,2), k = 2 -> 1.333333
items (10,1) (1,10) (10,1) (1,10) (5,5) (5,5), k = 3 -> 3.571429
## Why picking the best items one at a time fails
Sorting by a[i] / b[i] and taking the top k looks right and is wrong. In the second example the
individual ratios are 1, 0.667 and 1.5, so that rule picks items 3 and 1 for
(3+1)/(2+1) = 1.333, which happens to be correct here. Change the first item to (1, 100) and
its ratio stays at 0.01 while it becomes a terrible partner for anything; the point is that a
ratio of SUMS is not decided by the individual ratios, because a heavy item drags the denominator
of whatever it is paired with.
Trying every subset is exact and impossible: n choose k reaches astronomical counts by
n = 40.
## The trick that removes the division
Guess the answer x and ask whether it is reachable:
sum(a) / sum(b) >= x <=> sum(a) - x * sum(b) >= 0 <=> sum of (a[i] - x*b[i]) >= 0
The step is legal because every b[i] is at least 1, so sum(b) is strictly positive and
multiplying through does not flip the comparison. Now each item carries ONE number,
a[i] - x * b[i], and the items no longer interact. Take the k largest of them and see whether
they add to something not negative. Sorting once per candidate costs O(n log n).
This manoeuvre has a name, Dinkelbach's transformation, and it is the standard way to handle any "maximise a ratio" problem: fractional knapsack variants, maximum density subgraphs, minimum average cycles.
## Why the predicate is monotone
For a FIXED choice of k items, sum(a) - x * sum(b) is a straight line in x with slope
-sum(b), which is strictly negative. The best over all choices is a maximum of strictly
decreasing lines, so it too strictly decreases. Therefore "some choice reaches x" is true up to
a point and false after it.
## The bounds
lo = 0, since every a[i] is at least 0.
hi = max(a[i] / b[i]). The mediant inequality says a ratio of sums never exceeds the largest of
the individual ratios: if every a[i] <= M * b[i] then sum(a) <= M * sum(b). So no choice can
beat the best single item's ratio.
## The boundary that breaks a careless implementation
Taking the k largest means the k largest of a[i] - x*b[i], INCLUDING negative ones when
fewer than k values are positive. The choice is of exactly k items, not at most k, so a
check that only adds the positive values reports success too often and returns a ratio that
cannot be achieved.
## Related problems
Problem 805 uses the same subtract-the-candidate step on an average, which is this problem with
every b[i] equal to 1 and the choice restricted to a contiguous run.
## Cost
Time O(100 * n log n). Space O(n).
Constraints - `1 ≤ k ≤ n ≤ 10000` - `0 ≤ a[i] ≤ 10^4` - `1 ≤ b[i] ≤ 10^4` - every answer is at least `10^-9` away from a halfway rounding point at 6 digits
Input
The first line contains two integers n and k.
Each of the next n lines contains two integers a[i] and b[i], the worth and the weight of one item.
Output
Print the largest achievable ratio of total worth to total weight over exactly k items, with exactly 6 digits after the decimal point, in plain fixed notation and never in exponent form, alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.