Hi!

  I was solving some problems and I got to one that is very similar to this one, the differences are the size of n (n<=10000, and always even), of wi (wi<=60000) and that the amount of stones should be the same on both sides. The answer is the weight of both piles, not the difference.

  Is there a good algorithm to solve it with these conditions?

  Backtracking seems extremly slow as n is so big (maybe getting an initail aproximation with a greedy aproach and then doing some prunning might help, but I'm still sceptical).

  Also, I'm not very used to DP. I thought I might make a an array an mark all possible sums. I think I could do that in n*wi (same as Knapsack, right?) but the memory would be huge (if I have n/2 sums of wmax each it would make my array as big as 5000*60000 = 300 000 000). Is there a way to make this array smaller? Also, I have the problem that I have to keep how many numbers I used to make that number so if the number can be made in several way I don't now which to keep (for example: if I have 1,2,3,6 I could make 6 using 1,2 or 3 numbers, how to know which one is best?)

  Any ideas would be great!