algorithm - Splitting values into groups evenly

Question

Let me try to explain the situation the best I can.

Lets say I have 3 values

1, 2, 3

I tell an algorithm to split this values into x columns. Lets say x = 2 for clarification.

The algorithm determines that the group of values is best put into two columns the following way.

1st column    2nd column
---------------------------
1             3
2

Each column has an even number (totals, not literals) value.

Now lets say I have the following values

7, 8, 3, 1, 4

I tell the algorithm that I want the values split into 3 columns. The algorithm now tells me that the following is the best fit.

1st column    2nd column    3rd column
8             7             3
              1             4

Notice how the columns arent quiet even, but it is as close as it can get. A little over and a little under is considered ok, as long as the list is AS CLOSE TO EVEN AS IT CAN BE.

Anybody got any suggestions? Know any good methods of doing this?

Answer 1

I would do it like this:

• add all the values, let's call this S
• divide S by the number of columns, let's call this M.
• find a set of values of which the sum is M or as close as possible to M, using a knapsack algorithm (e.g. http://search.cpan.org/~andale/Algorithm-Knapsack-0.02/lib/Algorithm/Knapsack.pm (just a quick Google on knapsack))
• take the sum of the set of values and subtract it from S, let's call it T.
• divide T by the number of columns minus 1
• and repeat the algorithm