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$ – Yuval Filmus Feb 12 at 10:33
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$ – sean python Feb 12 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 at 22:03
  • $\begingroup$ What is the meaning of i in OPT[i,x]? $\endgroup$ – sean python Feb 13 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 at 14:54

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.