Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize $$ \left(\sum_{i \in S} a_i\right)\left(\sum_{i \notin S} b_i\right) $$

A naive solution is to iterate over the powerset of $\{1, 2, \dots ,n\}$ and find the maximum value, which is $O(n2^n)$. How to use dynamic programming to solve this?

Any comments would be appreciated.


If you could solve this problem, then you would be able to solve the NP-complete PARTITION problem. The partition problem asks whether a given set of positive integers $X$ can be partitioned into two equal parts. Given a set $X$ whose sum is $M$, choose an arbitrary ordering of its elements $X = \{x_1,\ldots,x_n\}$, and let $A=B=X$. Your problem asks to maximize $$ f(S) = \left(\sum_{i \in S} x_i \right) \left(M - \sum_{i \in S} x_i\right). $$ As a quadratic in $\sigma = \sum_{i \in S} x_i$, $f(S)$ is maximized at $\sigma = M/2$, at which we have $f = (M/2)^2$. This is achievable for some set $S$ iff $X$ can be partitioned into two equal halves.

| cite | improve this answer | |
  • $\begingroup$ Yes the partition problem is a special case of this problem. The DP solution of the partition problem gives me an idea: Maybe iterating over sum(A) * sum(B) is the answer (Actually the original problem is to find FPTAS algorithm so this could be the right path). Thanks for the tips. $\endgroup$ – Ian Chen Mar 5 '17 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.