Maximise Fractions

Question

Given a set of $n$ values of the form $(a, b)$ where $a$ and $b$ are integers. We need to choose $k$ values from the set such that sum(of all $a$'s in $k$)/sum(of all $b$'s in $k$) is maximized.

Answer 1

I have a relatively efficient algorithm, with time complexity $\mathcal O(n^3)$, assuming that all the $b_i$ are nonnegative; I don't have a good way of dealing with the possibly-negative case.

Suppose we want to know if it's possible to choose indices $i_1, \dots, i_k$ such that $$\frac{a_{i_1} + \dots + a_{i_k}}{b_{i_1} + \dots + b_{i_k}} \ge x.$$ We can now rewrite this equation as $$(a_{i_1} + \dots + a_{i_k}) - (b_{i_1} + \dots + b_{i_k})x \ge 0 \iff (a_{i_1} - b_{i_1}x) + \dots + (a_{i_k} - b_{i_k}x) \ge 0.$$ It's easy to test if this is possible to do: just sort all the values $a_1 - b_1x, a_2 - b_2x, \dots, a_n - b_nx$, choose the $k$ largest (or just choose the $k$ largest in $\mathcal O(n)$ time), and see if their sum is nonnegative.

(If the $b_i$ values can be negative, then this doesn't work, because the denominator $b_{i_1} + \dots + b_{i_k}$ might be less than $0$, reversing the inequality. Figuring out the best choice of pairs to use is then much harder, and I don't see how to deal with this.)

For different values of $x$, the order of the values $a_i - b_ix$ may be different as well, and so the choice of $k$ largest values may differ. But there's a limit to how much this order can vary. Consider two pairs $(a_i, b_i)$ and $(a_j, b_j)$. We have $$a_i - b_i x \ge a_j - b_j x \iff a_i - a_j \ge (b_i -b_j)x \iff \begin{cases}\frac{a_i - a_j}{b_i - b_j} \ge x, & b_i > b_j \\ \frac{a_i - a_j}{b_i - b_j} \le x, & b_i < b_j.\end{cases}$$ So the order of $a_i - b_i x$ and $a_j - b_j x$ changes only at $x = \frac{a_i - a_j}{b_i - b_j}$ (unless $b_i = b_j$, in which case their order never changes).

So if we think of the values $\frac{a_i - a_j}{b_i-b_j}$ (for all pairs $i$ and $j$) as breaking up $\mathbb R$ into $\binom{n}{2}+1$ disjoint intervals (at most), then on each interval, the order of $a_i - b_i x$ (and therefore, the optimal choice of pairs $(a_i,b_i)$) is consistent. So we can choose a test value of $x$ on each interval, choose the $k$ largest values of $a_i - b_i x$, and compute the quantity $\frac{a_{i_1} + \dots + a_{i_k}}{b_{i_1} + \dots + b_{i_k}}$ for them. For one of the test values, we'll see the largest possible value of this quantity.