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]

  • $\begingroup$ To start with we can fix n. But the problem asks to find the optimal n as well. $\endgroup$ – Manish Agarwal Jan 31 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.