Выбор рациональных чисел с максимальной суммой

Question

У меня есть n рациональных чисел. Из этого я должен выбрать m чисел, так что

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

например, если у меня есть 3 числа 1/1, 1/2, 2/4 и мне нужно выбрать 2 числа. Тогда комбинации будут

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

Предположим, у меня есть массив из n целых чисел, определяющих числители, и другой массив из n целых чисел знаменателей. И номер м. Какой будет стратегия?

Числа на входе не должны быть уменьшены рациональным числом. например, число может быть 4/6 и не обязательно 2/3.

РЕДАКТИРОВАТЬ: решение грубой силы будет пытаться все перестановки, выбрав m чисел из n. Затем примените приведенную выше формулу, чтобы найти результат, а затем посмотрите, какая комбинация дает максимальный результат.

Поэтому я хочу знать, существует ли какая-либо математическая формула или свойство или умный способ, чем метод грубой силы.

Answer 1

Я пойду на это.

Поскольку мы хотим максимизировать сумму числителей, разделенных на знаменатели, мы должны выбрать те числа, в которых разница между числителем и знаменателем максимальна. Это будет гарантировать, что максимальная сумма числителя выбрана для минимальной суммы знаменателя для m числа, которые дали бы нам максимальное значение дроби, в которой мы нуждаемся.

Например,

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

Следовательно, 1/1 а также 1/2, даст нам максимальное значение.

Если есть связь, мы можем просто выбрать дробь, которая имеет численно большие числители и знаменатели, так как это увеличит соотношение.

Например,

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

Надеюсь, это имело смысл.