在一个由n个数值对组成的集合中，大小为k的最小子集和最大子集的最大比率是多少？

Question

所以，假设你有一组形如{x，y}的值对，例如{1，2}，{1，3}和{2，5}。然后，您需要找到一个k个成对的子集（在这种情况下，假设k = 2），使得子集中所有x的总和除以所有y的总和的比率尽可能高。

请问是否有相关的理论或算法可以指导？ 这有点像最大子集和，但由于这些配对是“绑定”在一起的，所以引入了一种改变问题的限制。

- Jontahan

Answer 1

一开始我认为一个简单的贪心策略可以解决这个问题，但评论员指出了一些反例。

相反，我认为二分法应该可以解决。

假设我们想知道是否可能实现比率g。

我们需要添加k个向量来使其在一个梯度为g的直线上方。

如果我们将每个向量垂直于此线投影以获得值p1，p2，p3，则当且仅当p值的总和为正时，最终向量将在直线上方。

现在，使用投影值似乎正确的最佳解是选择最大的k。

然后，我们可以使用二分法找到可实现的最高比率。

数学证明

假设我们希望比率高于g，即

(x1+x2+x3)/(y1+y2+y3) >= g

=> (x1+x2+x3) >= g(y1+y2+y3)

=> (x1-g.y1) + (x2-g.y2) + (x3-g.y3) >= 0

=> p1 + p2 + p3 >= 0

其中pi的定义为xi-g.yi。

（注：此处g为常数）

- Peter de Rivaz

---

让我们有一对a = {2,4}，b = {1,2}和c = {3,3}。 第一和第二对将具有相同的个体比率。但是，如果我们选择两对，我们有两种情况看起来像这样： a＆c =（2 + 3）/（4 + 3）= 5/7。 b＆c =（1 + 3）/（2 + 3）= 4/5。 相同的个体比率，在与同一对匹配时产生不同的结果。 - Jontahan

这里不适用，因为将比率相加时，分子和分母分别相加和否则得到的结果不同。我的意思是，a/x + b/y != (a+b)/(x+y)，而此处的 OP 想要 (a+b)/(x+y)。 - vish4071

我认为这是一个反例，其中有三个集合（3, 1），（2001，1000），（2, 1），且k = 2。 贪婪算法建议使用集合[(3, 1)，（2001，1000）]，但[(3, 1)，（2, 1）]会得到更好的答案。 - Petar Petrovic

感谢提供反例 - 我已经提出了一种替代方法。 - Peter de Rivaz

你能否用图示更详细地解释一下你的意思？虽然这些想法很启发人，但我还是不太理解。 - גלעד ברקן

@גלעדברקן 我添加了一些数学内容，可能会有所帮助。 - Peter de Rivaz