The bruteforce is only correct way to solve this problem
you are to write function that will generate all permutations of(0,1) length n(where n-number of stones in pile)
than you have calculate weight of all stones that you took in concrete permutation and find minimal difference between 2 piles. that's all
sorry for poor eng

I found i really fast and simple solution for this one.
Main idea is:
1.Get 2 arrays(first one to store weights and sec to store 0 or 1 as includes in sum or not)
2.Find what sum would be best case
3.Go trough array and add to the sum until you get more than best sum
4.Now you need to make sum optimal,you do that this way:
    1.If current sum is greater than best you remove one element that is closest to current sum - best sum but only if by doing that you get better solution than the one you've got before
    2.If current sum is lest that optimal than you need to add one element that was not in sum and also you do that only if by doing that you get better solution than the one you've got before
5.If there were no changes in last pass you print result as abs(main sum - 2*current sum)

Hope you like it :)

i've got AC (0,015s and 212kb memory) using this algorithm

Edited by author 27.01.2012 20:35

Accepted    0.015    120 KB

start:
for each stone
  put stone in the other pile
  if the difference is greater than before
    then put it back
    else let it stay in this pile
end for
if the difference is smaller than before the for loop
  then goto start (do another pass)

make sure that you don't get an infinite loop. it happened and I got TLE at test 2

Edited by author 15.06.2012 18:22

Edited by author 15.06.2012 18:22

Hm...I developed another solution, but don't know why it is wrong. "Put" means add to the sum, like: left += element;
1. Sort stones in their weight from bigger to lower.
2. If there is only 1 stone - it is an answer.
3. If there are 2 stones - absolute of their difference is an answer.
4. Else: put first stone to left (or right) and second to ther right (or left).
5. Put next stone to the side which is lowerю
6. Repeat 5 until number of stones will be reached.
7. Print the absolute value of difference of the left and right.

Where I'm wrong?

Edited by author 30.06.2012 23:35

Edited by author 30.06.2012 23:41

The easiest one is brute-force

There are 2 cycles, one of them is generating (0, 1) sequence, (1 if we include the stone in 1-st set of stones and 0 if not), there are 2^n permutations. The second cycle checks, if we should include the stone in the 1-st set and adds its weight to the current set weight. We should find the best difference between 2 sets' weights, the weight of one set is current_weight, of the second, obviously, sum - current_weight (sum is weight of all the stones), and the difference is abs(current_weight - (sum - current_weight)) = abs(sum - 2 * current_weight).

But this is bad algorithm since it's complicity is O(n * 2^n), which is over 20 million in this problem in worst case. The DP algo complicity is O(n * sum), which is better in most of problems except this one, because if there are 20 stones and weight of each is 100000, then n * sum = 40 million, which is 2 times worse.

Edited by author 29.03.2013 14:57