Two bottles of numbers

[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

[krtxmrtz]

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

First I think it's important to know how large N can be. If N is low enough then you could try to solve the problem by considering the various permutations, but for a large N even a very fast computer may take plenty of time.

[zingix]

Thanks for the reply. N is <= 1000.

[krtxmrtz]

Thanks for the reply. N is <= 1000.

OK but, is it just a programming excercise? Is execution speed an issue?

[zaza]

It sounds to me like you'd want the following steps:

1. Sum all the numbers.
2. Divide by 2. This gives you what you'd have in each bottle if they were to come out equal.
3. Allocate the numbers to one bottle starting with the biggest number, subtracting off this total.
4. When your next number in the list will take your total below zero, skip it and move to the next.
5. Keep going until you reach the beginning of the list. And what is left goes in the other bottle.

So in your example, Total = 15. Ideal total per bottle = 7.5.

First bottle gets 5, Total = 7.5 - 5 = 2.5.
Skip 4.
Skip 3.
First bottle gets 2, Total = 2.5 - 2 = 0.5
Skip 1.


First bottle has 5, 2 = 7
Second bottle has 4, 3, 1 = 8.




zaza

[zingix]

Thank you zaza. Seems to work fine with linear runtime.

[krtxmrtz]

It sounds to me like you'd want the following steps:

1. Sum all the numbers.
2. Divide by 2. This gives you what you'd have in each bottle if they were to come out equal.
3. Allocate the numbers to one bottle starting with the biggest number, subtracting off this total.
4. When your next number in the list will take your total below zero, skip it and move to the next.
5. Keep going until you reach the beginning of the list. And what is left goes in the other bottle.

So in your example, Total = 15. Ideal total per bottle = 7.5.

First bottle gets 5, Total = 7.5 - 5 = 2.5.
Skip 4.
Skip 3.
First bottle gets 2, Total = 2.5 - 2 = 0.5
Skip 1.


First bottle has 5, 2 = 7
Second bottle has 4, 3, 1 = 8.




zaza

Pretty obvious... after someone has shown the way!