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$ Commented 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$ Commented 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$ Commented Feb 12, 2021 at 22:03
  • $\begingroup$ What is the meaning of i in OPT[i,x]? $\endgroup$ Commented 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$ Commented Feb 13, 2021 at 14:54

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.