arrays - 两个数组的最大子集和

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])

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

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 视为时间变量；我们感兴趣的是一维物理系统的演化，其中 n 个粒子的初始位置为 A，速度为 -B。每个粒子最多与其他粒子交叉一次，因此事件数为 O(n^2)。在交叉点之间，sum (a[i(j)] - t*b[i(j)]) 的最优值线性变化，因为 k 的子集相同是最优的。