2

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!

Reed
  • 123
  • 1
    Have you tried the greedy algorithm? – Calvin Lin Jun 11 '13 at 04: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$). – Caleb Stanford Jun 11 '13 at 04:59

1 Answers1

1

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&9\\5,7&2,4,3,10&error&\end{array}$$ and you can choose the best one.

Ross Millikan
  • 374,822
  • 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