My code sorts all the weights in descending order and then arranges them into two piles using algorythm:

1. Start with the heaviest stone;
2. If weight(pile1)<Weight(pile2) add current stone to pile1;
   Else add current stone to pile2;
3. If there are more stones current stone = next stone; Goto 1;

Consider the following example:
5
10 10 8 7 5

Your algo will give answer 4, while the correct one is 0. Use brute-force to solve the problem.

I think that the correct algorithm is using DP, like this:

If you figure out a way to find the sum of each possible subsets from {w0...wn}, and you know that w0+w1+..+wn = N... for some N, then the problem is reduced to find the set that gets closer to N/2.

IOW: Suppose you have a set and the sum of its elements is equal to N/2.. Then the sum of the other set is also N/2, so the difference is 0...
And the difference will always be minimal near N/2.. so if you can't get N/2, try finding the one closer to it.

the way I did it is:
...
  S := {w0,w1,...,wn}
  B := array(Bool, #(S), false)
  B[0] := true // you can always pic the empty set
  for i in S:
     for j in range(0, N):
        if B[j] = true:
           B[j+S[i]] := true
...
This gives you all possible sums of the possible subsets of S like this:

B[i] = true if there exist a set S' of S such that (sum(S') = i) holds.

Hope I wasn't very bad at my english.. :S

See ya
gaston770@gmail.com

gaston770 right , DP. This problem is same tpye as knap of problem.

W=Sum of w[i],i=1..n,
N=W/2;
find N=w[j1]+w[j2]+...+w[jk]:j1,j2,..jk in set[1..n].

Good luck.

Edited by author 07.04.2010 08:51

The size of input is too small, so you can try all the dispositions of N/2 stones. c(10,20) is less than 200000 ;)

why? I think the algorithm described by Freezing Sun would (and should) return the correct answer here: 1