How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{denominator sum}}$ is maximized. As in this case, selecting $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$ will result in $\frac{4+2+1}{2+3+2}$ = 1 which is maximized.

How can I select $k$ fractions which will always result in the maximum $\frac{\text{numerator sum}}{\text{denominator sum}}$ value?

Edit:

• Attempt 1: Sorting fractions in descending order. This passes a few test cases but that it's. This can also be proven by example that it is not the optimal solution. Let's say we have a list of 3 fractions sorted in descending order, $\frac{1}{2}$, $\frac{20}{59}$, $\frac{1}{3}$ and $k = 2$. The optimal solutions is $\frac{1+1}{2+3}$, not $\frac{1+20}{2+59}$.

For a list of fractions, define the ratio as (sum of numerator) / (sum of denominator).

Question: Can we find a list of k fractions with the ratio ≥ r, for some given r?

Let the sum of numerators be X, and the sum of denominators be Y, then we require X / Y ≥ r or X - rY ≥ 0. For a single fraction x / y, we can calculate x - ry. We pick the k fractions where x - ry is largest. If the sum X - rY ≥ 0, then we have a list with ratio ≥ r, otherwise there is none.

We have obvious lower and upper bounds for r (the k-largest and the largest value of any fractions). With binary search we can easily find a list with maximum ratio.

Responding to some comments: What I presented is the basic idea. There is plenty of room for improvement.

For example "we pick the k fractions where x - ry is largest" - that can easily be done without sorting the array, much faster than n log n. Start like Quicksort, but only process subarrays that you need to determine the k largest values.

And it's not just binary search, because each time you actually find a list of fractions and can update the lower or upper bound for r or both. (For example if the lower and upper bound were 6.0 ≤ r ≤ 10.0, you look for a list with ratio 8.0 and only find one with ratio 7.6, then in the next search you know 7.6 ≤ r < 8.0 is possible).

Since the lower bound for r is one that was actually achieved, you can also check which is the smallest eps for which you would have put a different fraction in the top k list of fractions.

StackExchange Computer Science Q#109187, answer score: 2