選擇最大總和的有理數

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。

編輯： 一個蠻力的解決方案將嘗試所有的排列，通過從n中選擇m個數字。然後應用上面的公式來查找結果，然後查看哪個組合給出最大結果。

所以我想知道是否有任何數學公式或財產或聰明的方式比蠻力的方式。

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 

希望它是有意義的。