From: Robert Klemme <shortcutter@...>
Date: 2008-10-22T17:51:51+09:00
Subject: Re: packing algorithm in Ruby

2008/10/22 John Small <jds340@gmail.com>:
>
>> this sounds as if you were looking for a solution of the knapsack
>> problem
>>
>> http://en.wikipedia.org/wiki/Knapsack_problem
>>
>> of combinatorial optimization/constraint programming.

And this is by far not a "simple case" as you said in your first
posting. Just the numbers are small. The problem class does not
change.

> 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.

I see one theoretical problem here: you have too much dimensions that
are allowed to change, namely the number of groups and the sum of one
group. Without limiting one of these, even the original array is a
proper solution, i.e. you have just one group with a "large" sum. You
will need to tackle this by reducing degrees of freedom here otherwise
you are unlikely to reach a satisfactory solution.

Kind regards

robert

-- 
remember.guy do |as, often| as.you_can - without end