-4

我有 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 个分母整数数组。和数字 m。会有什么策略？

输入中的数字不需要减少有理数。例如，一个数字可以是 4/6，不一定是 2/3。

编辑： 蛮力解决方案将通过从 n 中选择 m 个数字来尝试所有排列。然后应用上面的公式来找到结果，然后看看哪个组合给出了最大的结果。

所以我想知道是否有任何数学公式或属性或比蛮力方式更聪明的方式。

4

1 回答 1

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

希望这是有道理的。

于 2017-04-16T05:40:40.423 回答