两个数组中的最大子集和

Question

我很不确定这个问题可以在多项式时间内完成。

问题：

Given two arrays of real numbers,

A = (a[1], a[2], ..., a[n]), 
B = (b[1], b[2], ..., b[n]),  (b[j] > 0, j = 1, 2, ..., n)

and a number k, find a subset A' of A (A' = (a[i(1)], a[i(2)], ..., a[i(k)])), which contains exactly k elements, such that, (sum a[i(j)])/(sum b[i(j)]) is maximized, where
j = 1, 2, ..., k.

例如，如果 k == 3，并且结果为 {a[1], a[5], a[7]}，则：

(a[1] + a[5] + a[7])/(b[1] + b[5] + b[7])

应该比任何其他组合都要大。有什么线索吗？

- Geni

---

我猜99.99%的概率这是NP-Hard问题，但我可以问一下你在哪里看到这个问题？总的来说，这是一个非常好的问题。 - Saeed Amiri

谢谢您的回复。我将一个真实的负载均衡问题简化为这个抽象版本。我已经花费了两天以上的时间来解决这个问题。现在，我也有一种感觉它是NP难问题。 - Geni

有 n 个选择 k 种可能的比率，因此设置了复杂度的上限。我正在考虑一种方法来选择最大的比率 a[i]/b[i] 开始，然后选择使 k=2 的情况尽可能大的索引。这样，在该步骤中，您必须比较 n-1 个比率。然后继续选择第三个索引。证明一旦选择了 k 个索引，这将始终给出最佳比率可能很难（或者可能不是真的！），但是尝试证明可能会提供一些见解。 - JohnPS

嗨John，非常感谢你的回答。昨天我试图证明你的算法的正确性，但最终得到了一个反例。请检查这个A = [10, 2, 1, 0.2]，B = [7, 3, 2, 1.34]，k = 3。 - Geni

a[i] 和 b[i] 可以为零或负数吗？ - Anonym Mus

@Geni - 我怀疑会有这样的反例。 - JohnPS

Answer 1

假设 B 的项都是正数（听起来这种特殊情况可能对您有用），则存在一个 O(n^2 log n) 算法。

让我们首先解决一个问题，即对于特定的 t，是否存在一种解决方案，使得

(sum a[i(j)])/(sum b[i(j)]) >= t.

清除分母后，该条件等价于：

sum (a[i(j)] - t*b[i(j)]) >= 0.

我们所要做的就是选择 a[i(j)] - t*b[i(j)] 的前 k 个最大值。

现在，为了解决当 t 未知时的问题，我们使用动态算法。将 t 视为时间变量；我们关心一维物理系统中具有初始位置 A 和速度 -B 的 n 个粒子的演化。每个粒子最多会与其他粒子相交一次，因此事件数为 O(n^2)。在相交之间，sum (a[i(j)] - t*b[i(j)]) 的最优解线性变化，因为最佳的子集相同。

- Per

---

我怀疑存在一种使用线条排列和计算几何机制的O(n^2)算法。 - Per

+1 非常棒的答案。我从未见过像这样的东西。我很好奇这种方法是否适用于更大范围的问题，以及这种解决方案的名称是什么...还是你只是凭空想出来的？ - JohnPS

@JohnPS 动力学算法是计算几何学家喜欢的一种设计技术。当您有一个连续参数（解释为时间）和一个“物理系统”，除了有限次之外，它会很好地变化时，这些算法就可以应用。 - Per

Answer 2

如果B可以包含负数，那么这个问题就是NP-Hard。

因为这个问题的NP-Hard性质：

给定k和数组B，是否存在一个大小为k的B的子集其元素之和为零。

在这种情况下，A就不重要了。

当然，从你的评论中看来，B必须包含正数。

- user127.0.0.1

---

嗨！谢谢你的回复。抱歉，我忘了提到B只包含正数。 - Geni