# Selecting rational numbers with maximum ratio of (sum of nummerator)/(sum of denominators)

I have n rational numbers. Out of that I have to select m numbers such that

sum of numerators of m numbers /sum denominators of m numbers is maximum.


e.g. if I have 3 numbers 1/1, 1/2, 2/4 and I have to select 2 numbers. Then combinations will be

If 1/1, 1/2  are used then 1+1/1+2 = 2/3
If 1/1, 2/4 are used then  1+2/1+4=3/5
If 1/2, 2/4 are used then  1+2/2+4=3/6=1/2

Maximum is 2/3


Suppose I have array of n integers specifying numerators, and other array of n integers of denominators. And number m. What will be strategy ?

The numbers in input need not be reduced rational number. e.g a number can be 4/6 and not necessarily 2/3.

EDIT: A brute force solution will be try all permutations by selecting m numbers from n. And then apply above formula to find result and then see which combination gives maximum result.

So I want to know if there is any mathematical formula or property or a smarted way than brute force way.

EDIT. Answer I received from stackoverflow. Let me know if it correct

Since we want to maximise the sum of numerators divided by denominators, we should choose those numbers where the difference between the numerator and the denominator is maximum. This would ensure that the maximum sum of numerator is chosen for the minimum sum of denominator for m numbers, which would give us the maximum value of the fraction we need.

For ex,

nums - 1/1, 1/2, 2/4
diff - 0  , -1 , -2
max is 2/3 using 1/1 and 1/2


Therefore, 1/1 and 1/2, would give us the max value.

If there is a tie, we can simply choose the fraction which has numerically larger numerators and denominators since that would increase the ratio.

For ex,

nums - 1/1, 1/2, 2/4, 2/3
diff - 0  , -1 , -2 , -1
max is 3/4 using 1/1 and 2/3

• The answer is obviously incorrect. Try the set $({2\over1},{3\over1,}{199\over100})$. Choosing by the difference, you'll have ${3+199\over1+100}=2$. Now how about ${2+3\over1+1}$? Commented Dec 1, 2017 at 11:30