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

Question

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}$.

Answer 1

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.

Answer 2

Based on insights in the other answers, one simple and quite efficient algorithm is:

1. Set $r = 0$.
2. Choose the top $k$ values of $x_i - ry_i$ (using, e.g., quickselect in $O(n)$ time).
3. Sum the chosen $x_i$ into $X$ and the $y_i$ into $Y$.
4. If $X - rY > 0$:
   • Set $r = X / Y$. (This will strictly increase $r$.)
   • Go to step 2.

The idea is to determine a set of lines that produce the highest possible sum at the current $r$ value, and then "slide right" along the sum of those lines (which is also a line) until it intersects the $x$ axis: where that intersection occurs is an achievable $r$ value, but it may not be the maximum possible such value, because there may be some other combination of lines that does even better. When this is no longer possible, we have found the maximum $r$.

Every time $r$ is successfully updated in step 4, at least one of the chosen $k$ lines is replaced at the following step 2 with a different line that is above it everywhere at and to the right of the current $r$ value; the replaced line will never be chosen again, so the loop executes at most $n-k$ times. Step 2 can be performed using quickselect in $O(n)$ time, for $O(n^2)$ time overall (and just $O(n)$ time when $n-k = O(1)$). Note that because we do not necessarily process each segment of the piecewise linear maximum function, there will be many inputs for which the loop executes less than the full $n-k$ times.

Removing dominated lines

It is also possible to get rid of "dominated" lines after step 2 without altering the time complexity -- this should speed things up in practice. Line $i$ is dominated if $x_i - ry_i < A$ and $y_i > B$, where $A$ is the smallest of the $k$ chosen $x_i - ry_i$ values, and $B$ is the largest of their denominators $y_i$.

Answer 3

Extending gnasher's observation:

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.

For each fraction $\frac{x}{y}$ the graph of $x - ry$ against $r$ is a straight line. The sum of the $k$ highest lines is a convex monotonically decreasing piecewise linear function with discontinuities only possible when two of the straight lines intersect. Therefore we can take the pairwise intersections of the lines to find all values of $r$ at which the $k$ highest lines might change, use bisection as described by gnasher to find the linear piece where the sum crosses zero, and then interpolate linearly within that piece to find the exact value of $r$.

Cost:

• $\Theta(n^2)$ to find the intersections
• $O(n^2 \lg n)$ to sort them
• Finding the $k$ highest can be done in $O(n)$ time using quickselect, so $O(n \lg n)$ time for the bisection
• $O(n)$ time for the final interpolation

---

As an optimisation, it's not necessary to do the full sort. Using quickselect to partition at the median, you can test whether the sum at that median value is above or below zero and then recurse only on half of the intersections. This gives an algorithm with $\Theta(n^2)$ running time.

---

This description of the curve also gives a bisection algorithm without preprocessing. If you have a value of $r$ where the curve is above the line and a value where it's below the line, you can extrapolate the linear segments of the line at those two values to find their intersection point, which must be at an intermediate value of $r$. When both values are on the same linear segment you interpolate to find the root. There is an important subtlety in the selection of the top $k$ lines at $r$: depending on whether it's a lower or an upper bound you need to break ties differently to get the correct gradient.

This takes at most $n - k$ steps (as observed by j_random_hacker - I'm kicking myself for not spotting it), so $O(n^2)$ time overall, but as with the algorithm they present it has a good chance to do better than worst case.

Answer 4

If you sort the fractions by their ratios in descending order, and take the k fractions with largest ratio, that gives you a lower bound. Why would this not be optimal?

The k-th fraction, the k-1st fraction and so on pull the average down. Say k = 10, you have five fractions 100/10, five fractions 20/10, and 100 fractions 1/1. Taking the ten largest ratios gives a result 600 / 100 = 6. Taking the five largest, and five times 1/1 gives 505 / 55 > 9. So you want some large ratios, combined with small numerators and denominators.

In my example, can we get a result of 7? We obviously take the five fractions with a ratio ≥ 7, giving 500/50. Assume we add 5 more fractions with a sum X / Y, then we need (500 + X) / (50 + Y) ≥ 7, or 500 + X ≥ 350 + 7Y, or 150 + X ≥ 7Y or 7Y - X ≤ 150. For each fraction x / y we define its "badness" as 7y - x, then we need to find 5 fractions with a total badness ≤ 150. We take the fractions with the least badness; if the sum is ≤ 150 then we found 10 fractions with ratio ≥ 7, otherwise there are no such 10 fractions. In any case, we may have found 10 better points, and we adjust the ratio we are looking for.