1
$\begingroup$

I was given this problem in class, and I have no idea how to solve it. The problem is:

"Given a list of positive integers, divide the numbers into 2 groups such that the difference between the sum of each group is minimal, print that difference. The algorithm must be efficient."

I guess by efficient they mean do not just brute force every option, any ideas?

I tried summing all the numbers and dividing by 2, then the problem is equivalent to finding a group that is the closest to that number, also now you can go over all the options but once you get to a point where you can only add numbers but your above that number you can stop.

$\endgroup$
1
  • 1
    $\begingroup$ This is a version of the NP-complete problem PARTITION. $\endgroup$ Feb 12, 2021 at 10:33

1 Answer 1

3
$\begingroup$

As Yuval Filmus points out, this is an optimization version of the PARTITION problem. The problem is weakly NP-complete, so any polynomial time solution to your problem would immediately solve partition (simply check if the minimum difference between the sums of the two sets is $0$).

You can solve the problem in pseudo-polynomial time $O(nS)$, where $S$ the sum of the input integers, using dynamic programming, or in time $O(n \cdot 2^{n/2})$ using the split-and-list technique. Pick the best of the two algorithms depending on the value of $S$.

The dynamic programming algorithm is as follows. Let $A = \{a_1, \dots, a_n\}$ be the input (multi-)set of numbers, and let $S=\sum_{a \in A} a$. Consider a partition of $A$ into two sets $B$ and $C$, and assume w.l.o.g. that $\sum_{b \in B} b \le \sum_{c \in C} c$ (since otherwise you can swap $B$ and $C$). The cost (to minimize) of this partition is: $$ \sum_{c \in C} c - \sum_{b \in B} b = \left(S- \sum_{b \in B} b\right) - \sum_{b \in B} b = S - 2 \sum_{b \in B} b. $$

Showing that the problem is equivalent to finding a subset $B$ of $A$ whose sum of elements is at most $\lfloor S/2 \rfloor$ and, subject to this constraint, it is maximized.

For $i=0, \dots, n$, and $x=1,\dots,\lfloor S/2 \rfloor$, let $OPT[i,x]$ be true if and only if there exists a subset $B$ of $\{a_1, \dots, a_i\}$ with $\sum_{b \in B} b = x$.

Then $OPT[0,0]=\top$ and, for $x>0$, $OPT[0,x]=\bot$.

If $i>0$: $$ OPT[i,x] = \begin{cases} OPT[i-1,x] \vee OPT[i-1,x-a_i] & \mbox{if $a_i \le x$} \\ OPT[i-1,x] & \mbox{otherwise} \end{cases}. $$

There are $O(nS)$ values $OPT[i,x]$ and each of them can be computed in constant time (in increasing order of $i$). The maximum value of $\sum_{b \in B} b$ is $\max \left\{ x \in \{0, \dots, \lfloor S/2 \rfloor \} \mid OPT[n, x] = \top \right\}$.

$\endgroup$
4
  • $\begingroup$ Could you elaborate on the dynamic programming approach? Should i check all possible partition's and compute the sum using dynamic progrmming? $\endgroup$ Feb 12, 2021 at 22:01
  • $\begingroup$ If you check all possible partitions you're already using $\Omega(2^n)$ time. I'm editing my answer with the dynamic programming algorithm. Give me ~10 minutes. $\endgroup$
    – Steven
    Feb 12, 2021 at 22:03
  • $\begingroup$ What is the meaning of i in OPT[i,x]? $\endgroup$ Feb 13, 2021 at 13:19
  • $\begingroup$ @seanpython, it means that we are only considering the first $i$ elements of $A$, i.e., the set $\{a_1, \dots, a_i\}$. $\endgroup$
    – Steven
    Feb 13, 2021 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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