------art_26278_31381972.1224660135390
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On Wed, Oct 22, 2008 at 8:05 AM, John Small <jds340 / gmail.com> wrote:

> Axel
>
> Thanks for the links, the gecoder one looks very interesting I'll read
> more on that later on. For the time being I'm close to solving the
> problem myself using Ruby's array magic coupled with
> array.in_groups_of() from Rails ActiveSupport.
>
> There's an additional constraint on my packing; the lists have to be in
> order. In essence what I do is break an array of records into groups,
> sum each group over an integer attribute on the items in the group, if
> the group sum is within bounds then select that group. I then remove the
> selected items from the initial list and do the whole thing again with a
> larger value in .in_groups_of. I'll post up the code when I've got it
> working so everyone can comment and improve it.
>

A way to solve your problem goes as follows. First write a method
sub_arrays(max) that builds the sub-arrays given a maximal sum. This should
be easy enough; just fill up an array until the sum would exceed that
maximum in which case you start a new array and fill that one up. Then
either you have 3 columns or less, or you have more. Next observe that that
maximal sum can never go beneath ar.sum / 3, and that it doesn't need to go
above ar.sum / 3 + ar.max. So all you need to do then is to do a binary
search on that range for the minimum m for which sub_arrays(m).length < .
This algorithm is O(log(ar.max) * ar.length).

Peter

------art_26278_31381972.1224660135390--