最大的子集和两个数组

本文介绍了最大的子集和两个数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我甚至不知道这是否可以在多项式时间内完成。

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

问题：

实数给定两个数组，

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 [1（1）]，   A [1（2）]，...，A [1（K））），其中只包含 K 元素，使得，（求和[我（J）]）/（总和B〔我（J）]）最大化，其中 J = 1，2，...，K 。

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, wherej = 1, 2, ..., k.

例如，如果 K == 3 和 {A [1]中，[5]，一个[7]} 的结果，那么

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?

推荐答案

假设 B 的项是正的（这听起来好像这种特殊情况下可能是有用的你），有一个为O（n ^ 2 log n）的算法。

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.

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

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.

我们所要做的就是选择 K 的最大值 A [1（J）] - T * B〔我（J） ] 。

现在，为了解决这个问题，当 T 是未知的，我们用动力学的算法。想想 T 作为一个时间变量;我们感兴趣的是一维物理系统的演化与 N 其初始位置颗粒 A 和速度 -B 。每个粒子横穿彼此粒子至多一个时间，所以事件数是为O（n ^ 2）。在跨越之间，的和的最佳（A [1（j）条] - 吨* B [I（j）条]）线性变化，由于相同的子集氏/ code>是最佳的。

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.