CODEWITHSUNDEEP
arraysalgorithmmathsubset-sum
Geni
Geni

Reputation: 707

Maximum subset sum with two arrays

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?

Upvotes: 4

Views: 1321

Answers (2)

user127.0.0.1
user127.0.0.1

Reputation: 1337

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

Because of the NP-Hardness of this problem:

Given k and array B, is there a subset of size k of B which sums to zero.

The A becomes immaterial in that case.

Of course, from your comment it seems like B must contain positive numbers.

Upvotes: 2

Per
Per

Reputation: 2624

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.

Upvotes: 3

Related Questions