两个数组的最大子集和

发布于 2024-12-15 14:43:56 字数 592 浏览 2 评论 0原文

我什至不确定这是否可以在多项式时间内完成。

问题：

给定两个实数数组，
A = (a[1], a[2], ..., a[n]), 
B = (b[1], b[2], ..., b[n]), (b[j] > 0, j = 1, 2, ..., n)
和一个数字k，找到A的子集A' (A' = (a[i(1)], a[i(2)], ..., a[i(k)]))，其中恰好包含 k 个元素，这样，(sum a[i (j)])/(sum b[i(j)]) 最大化，其中
j = 1, 2, ..., k。

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

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

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

原文

I am not even sure if this can be done in polynomial time.

Problem:

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.

For example, if k == 3, and {a[1], a[5], a[7]} is the result, then

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

should be larger than any other combination. Any clue?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

梦冥 2024-12-22 14:43:56

假设 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.

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

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

Assuming that the entries of B are positive (it sounds as though this special case might be useful to you), there is an O(n^2 log n) algorithm.

Let's first solve the problem of deciding, for a particular t, whether there exists a solution such that

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

Clearing the denominator, this condition is equivalent to

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

All we have to do is choose the k largest values of a[i(j)] - t*b[i(j)].

Now, in order to solve the problem when t is unknown, we use a kinetic algorithm. Think of t as being a time variable; we are interested in the evolution of a one-dimensional physical system with n particles having initial positions A and velocities -B. Each particle crosses each other particle at most one time, so the number of events is O(n^2). In between crossings, the optimum of sum (a[i(j)] - t*b[i(j)]) changes linearly, because the same subset of k is optimal.