2

You have 2 arrays a and b, each contains n numbers. You have a number k.

[n] = the index set 1...n

We want to find the subset S of [n] such that the sum of elements indexed by S in a is at least k, and the sum of elements indexed by S in b is as small is possible.

I'm unable to find even a polynomial time algorithm for this. I'd be grateful for any ideas on how to solve this.

RBarryYoung
  • 55,398
  • 14
  • 96
  • 137
user36338
  • 23
  • 2
  • Is this homework? What approaches have you come up with so far? The subset S is not necessarily contiguous elements, right? – hatchet - done with SOverflow Jul 31 '12 at 16:41
  • The following similar questions may give you some ideas: http://stackoverflow.com/questions/8099334/maximum-subset-sum-with-two-arrays http://stackoverflow.com/questions/443712/algorithm-to-find-subset-within-two-sets-of-integers-whose-sums-match/443950#443950 – hatchet - done with SOverflow Jul 31 '12 at 16:50
  • This is not homework. I am reading up a problem on allocating resources to players which reduces to this in a special case. I see now that this is NP-complete. Knapsack can be solved in polynomial time up to any accuracy, and we can also reduce this to knapsack by binary searching on target value. So, I guess this can also be solved in polynomial time to any accuracy, I'll have to verify this though. – user36338 Aug 01 '12 at 08:09

2 Answers2

0

Are you interested in at least polynomial, right? Easy to have exponential iterating all masks for the set and checking both conditions (sum >= k and compare what we had before in sum of b and now)

Roman Dzhabarov
  • 521
  • 4
  • 10
0

A general solution to this problem is NP-complete, because it subsumes the knapsack problem. However, as with the knapsack problem, you may be able to address it constructively (in "pseudopolynomial time") using dynamic programming.

To see this: given a knapsack problem with knapsack size T and object sizes c[i], compose a problem as described in your question such that a[i]==b[i]==c[i] and k == sum(c[i]) - T.

Then, the solution to the knapsack problem is the set of indices not in S:

sum(c[i] *not* indexed by S) == sum(c[i]) - sum(a[i] indexed by S)

T == sum(c[i]) - k

Note that S satisfies knapsack constraint sum(c[i] *not* indexed by S) <= T if and only if the problem constraint sum(a[i] indexed by S) >= k holds.

sum(c[i] *not* indexed by S) == sum(c[i]) - sum(b[i] indexed by S)

Since a solution to the posed problem minimizes sum(b[i] indexed by S) over valid S, sum(c[i] *not* indexed by S) is maximized over valid S, and is an optimal solution of the knapsack problem.

comingstorm
  • 25,557
  • 3
  • 43
  • 67