Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for a way to group numbers into 3 groups, which each group has a sum as close to others as possible. And the order of original list is preserved.

For example , here is a list:

5,7,2,4,3,10
I should group them into (5,7) (2,4,3) (10)
the sum for each group is (12) (9) (10)

My initial thought is to add up until one group is greater than Sum/3, then move to next. But the above list will become:

edit: wrong number used, sorry for the error.
avg=10.3
groups: (5,72) (4,3,10) ()

I am thinking about adding more conditions to the addup process, But there are always edge cases not covered. As a stubborn programmer, I'd wish to have something working intrinsically correct rather than relying on conditions to cover edge cases.

The original problem: Trying to arrange a number of tables into 3 columns layout without breaking individual tables. Then each column should have similar height. The numbers in the example represent the height of each table.

Thanks!

share|improve this question
1  
Have you tried the greedy algorithm? –  Calvin Lin Jun 11 '13 at 4:32
1  
The above list does not become (5,7) (2,4) (3,10) as you state. $\text{Sum}/3$ is equal to $10.\overline{3}$, so in fact you would either get (5,7) (2,4, 3, 10) () (if adding up each group individually until it passed 10.3) or (5,7) (2,4,3) (10) (if considering the total sum so far and breaking off when it passes $\text{Sum}/3$ and $2\cdot\text{Sum}/3$). –  Goos Jun 11 '13 at 4:59
add comment

1 Answer

Note that two of your groups have sum less than $\frac {Sum}3$, and at least one of them will. So you should consider placing the breaks just before or just after you cross $\frac {Sum}3$ For the first group, you would then have the possibility of $5$ or $5,7$. In the first case, you can then have $7,2$ or $7,2,4$ In the second, you can have $2,4,3$ or $2,4,3,10$. So the choices are $$\begin {array} {r|r|r|r|r}first&second&third&max sum&min sum\\\hline 5&7,2&4,3,10&17&5\\ 5&7,2,4&3,10&13&5\\5,7&2,4,3&10&12&10\\5,7&2,4,3,10&error&\end{array}$$ and you can choose the best one.

share|improve this answer
    
this looks better, and not computational expensive. I'll try it out in the program tonight. Post back later. –  Reed Jun 11 '13 at 20:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.