Suppose I have $N$ pairs of positive numbers $(a\_1, b\_1), (a\_2, b\_2), \dotsc, (a\_N, b\_N).$ and I want to find a subset of $M$ of them maximizing
$$
\frac{\sum\_{j=1}^M a\_{i\_j}}{\sum\_{j=1}^M b\_{i\_j}}.
$$


Can this be done in polynomial time?



Optimization algorithm sought
The paper ["Dropping Lowest Grades"](http://cseweb.ucsd.edu/~dakane/droplowest.pdf) by Daniel M. Kane and Jonathan M. Kane addresses this question in the context of dropping $r$ quiz grades from a collection of weighted grades.


The solution described there is fundamental the same as that in [David Eppstein's answer](https://mathoverflow.net/a/350600/1079). However, there is also a discussion of a practical implementation that may be even faster in practice.


