Dividing a set into two subsets the optimal way (May be similar to the knapsack problem)

We have n stones having weight m[1]..m[n], and two sacks. We put each stone into first or second sack; the resulting sacks weights with stones become S[1] and S[2] (the sacks themselves have no weight). The task is to divide stones so that the weight difference |S[1] - S[2]| is minimal

Let me ask you if my approach is right:

1) let's sort the stones descending.

2) i=1

3) A is the index of the lightest sack (or first if they have equal weight)

4) put m[i] stone to S[A], S[A] += m[i]

5) i++

6) if there are stones left (i <= n) then goto 3

-
This is as much [set-theory] as it is [geology]. This is also verge off topic. –  Asaf Karagila Dec 1 '11 at 13:15
jsfiddle.net/MBgeC/22 –  Dan Dec 1 '11 at 19:51

This is an NP-hard optimization variant of the PARTITION problem which is NP-complete (for deciding if it's possible to split them equally). The greedy algorithm you propose is a special case of an algorithm for scheduling with minimum makespan, and can be shown to be a 4/3 approximation for the problem of minimizing the max load on either element (which is the same as your problem for the purpose of computing the exact answer). However, there's a relatively simple dynamic programming solution that runs in pseudopolynomial time.

-
Sorry, is the algorithm given here jsfiddle.net/MBgeC/22 the one you are talking about in the last sentence? –  Dan Dec 29 '11 at 8:31
maybe: it's hard to tell from the code. –  Suresh Venkat Dec 29 '11 at 19:50

This approach does not work.

Assume your weights are 1,2,2,5. Then the minimal difference is 0, which can only be attained by putting the first three stones in one suck, and the last stone in the other.

Your algorithm, however, will divide the weights such that the difference is 4.

Notice, however, that this problem can be transposed. Assume you have a single sack, but for each weight you can choose if it's either positive or negative (laws of physics be damned). The weight in the new sack is the difference of weights between the original sacks, where the sign decides which of the original sacks the weight goes to.

Taking it a step further, this translates to the following problem: Given a list of positive numbers, find a way to sign them such that the absolute value of the sum is minimal.

This problem can be solved with dynamic programming with runtime complexity of $o(n^2)$, where $n$ is the amount of numbers (under the relaxing assumption that addition/subtraction of two numbers has constant complexity).

Update:

I mistakenly thought you sort them ascending and not descending.

For the descending case your solution seems to work (and I like it better than my proposed solution).

To prove it assume that there's an optimal solution which gets a lower weight difference than your result. Choose the sack with the biggest rock to be S[0], and let i be the maximal index such that the rock m[i] was placed differently than your algorithm would given the current state of the sacks just before it was placed.

If m[i] is the last stone and the sacks aren't of equal weight then obviously the solution is not optimal (the last stone was put on the heavier pile).

If m[i] is the last stone and the sacks are of equal weight then, since this is the lightest stone, then your algorithm would've reach the same difference.

If m[i] is not the last stone, then had you put it on the other stack, your algorithm would produce a better result, contradicting the given solution being optimal.

-
No, @Shai Deshe, you are wrong jsfiddle.net/MBgeC/22 –  Dan Dec 1 '11 at 15:41
Please update your answer, Shai –  Dan Dec 1 '11 at 15:41
@Dan, please be more specific. If you want my help the least you could do is to point out what you didn't like about my answer. –  Shai Deshe Dec 1 '11 at 15:44

Suppose your weights are 5,4,3,3,3. If I understand your algorithm, you will put 5 in sack 1, then 4 in sack 2, then 3 in sack 2, 3 in sack 1, 3 in sack 2, winding up with 8 in sack 1 and 10 in sack 2, for a difference of 2. But you could have made the difference zero by putting 5 and 4 in one sack, 3, 3, 3 in the other.

I think the problem is indeed the knapsack problem, or close enough as to make little difference; it is undoubtedly NP-complete. Your algorithm is one of many approximation algorithms that have been suggested. I'm sure that somewhere in the literature there are theorems saying that it never misses by more than such-and-such a percentage, but unfortunately I don't know the literature well enough to give citations or precise results.

-