Two bottles of numbers

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

Quote:

---

Originally Posted by 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

---

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.

Thanks for the reply. N is <= 1000.

Quote:

---

Originally Posted by zingix

Thanks for the reply. N is <= 1000.

---

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

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

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

Quote:

---

Originally Posted by 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

---

Pretty obvious... after someone has shown the way! :) :thumb: