Seperate numbers into two bottles

[zingix]

Hi all,

Do you have any suggestions for the following problem:

You've got n-Numbers (e.g. 1,2,3,4,5). Put them into two bottles, so that the difference between these two bottles is minimal. Output should be the minimal differnece.

First bottle contains: 3,4 (3+4=7)
Second bottle: 1,2,5 (1+2+5=8)

So the solution would be: 1 (minimal difference)

Any ideas how to solve that with a program?
Thanks

[JimK]

Just a thought....

I think that this problem is NP-hard, so there is no known polynomial algorithm which can solve it.
I think you can use the decreasing-time-list algorithm but it doesn`t gives you the optimal partition.

[zingix]

Thanks for your reply. I found quite a good solution with a Knapsack-algorithm.

[TheCPUWizard]

The Knapsack methodology is fairly well suited to this class of problems. Another solution would be the "Alternate Deifferential" series.

The effectiveness (i.e. computational speed) of both approaches would likely depend on the data content, but both are on the same O(...) scale..