The maximum sum of a subset with two arrays

Question

I’m not even sure that 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 the number k , find the 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)]) 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]) 

must be larger than any other combination. Any clue?

Answer 1

Assuming that the entries of B positive (it seems that this special case may be useful to you), there exists an O(n^2 log n) algorithm.

Let first solve the problem of solving for a specific t whether there exists a solution such that

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

Cleaning the denominator, this condition is equivalent

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

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

Now, to solve the problem when t unknown, we use the kinetic algorithm. Think t is a temporary 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 no more than once, therefore the number of events is O(n^2) . Between the intersections, the optimal sum (a[i(j)] - t*b[i(j)]) varies linearly, since the same subset k is optimal.

Answer 2

If B can contain negative numbers, then this is NP-Hard.

Due to the NP-hardness of this problem:

For k and array B, there is a subset of size k of B that sums with zero.

In this case, A becomes immaterial.

Of course, from your comment, it seems that B should contain positive numbers.