I came across this simple looking but puzzling question recently. There is a set of N tuples given [(a1,b1), ..., (aN, bN)], where a are real numbers and b are positive real numbers. We need to choose n tuples from this set (n < N) such that AVG(a)/AVG(b) for this chosen set is the maximum.
I thought of sorting the tuples based on a/b values and taking the top n, but that is clearly not right. Any hints on to how to go about it? If not exact, an approx solution is also acceptable [for the second case where 'a' has Gaussian noise added to it]