From: John Small <jds340@...>
Date: 2008-10-22T15:05:43+09:00
Subject: Re: packing algorithm in Ruby


> 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.
> 
> For the latter, there is gecode and its Ruby bindings, gecoder.
> Have a look at its square tiling example:
> 
> http://gecoder.rubyforge.org/examples/square-tiling.html
> 
> Best regards,
> 
> Axel
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.

John




-- 
Posted via http://www.ruby-forum.com/.