Partition problem minimum difference between sum of 2 sets

[temper_3243]

hi,
i have n numbers , n <= 10^5. Each number 0 <= k <= 2^30. Now i want to split them into 2 sets such that difference of sum of sets is minimum.

Can someone suggest a good algorithm with approximation which works for these cases very well ? Which cases doesn't it work well ?

Regards
Terry

[N|N0]

I'd consider using knapsack.
http://www.nist.gov/dads/HTML/knapsackProblem.html

[temper_3243]

I don't understand how to reduce this to a knapsack problem. Can you give the algo or an example

[Learnable]

A number either belongs to set 1 or to set 2, and you can recurse on that. But with the amount of numbers you have, you'll probably have to find an approximate solution, or find a good way to evaluate partial solutions.

If the numbers are uniformly distributed, sort the numbers, and then alternatively add numbers to each set from both ends of the list.

For example, you have 1,2,3,4,5,6.

You start with 1 and 6. Add both to set 1. Then you get 2 and 5 - add them to set 2. When you get the last two numbers, add one to set 1 and another to set 2. If n is odd, add the last number to the set with the lower total.

So,

Set 1: 1 6 3
Set 2: 2 5 4

Once you do that, try to randomly exchange numbers between the sets to improve upon the solution.

[kp]

I don't understand how to reduce this to a knapsack problem. Can you give the algo or an example

1. Calculate Capacity = (sum of all numbers)/2
2. Now all you need is to find maximum sum of Xi that <= Capacity. That is exactly knapsack problem, and you probably need some approximate algorithm of solving knapsack problem