Subj : Re: stacking algorithm
To   : comp.programming
From : Omri Barel
Date : Thu Aug 04 2005 12:11 pm

Michael Jørgensen wrote:
> "nobiscuit" <nobiscuit@gmail.com> wrote in message
> news:1123109611.311910.111650@f14g2000cwb.googlegroups.com...
> 
> 
>>I figure this has to be a pretty common problem.  I did a google search
>>but didn't find anything.  Can anyone suggest an algorithm which is
>>similar or does anyone have any cunning suggestions for an algorithm?
> 
> 
> This sounds exactly like the "bin packing problem". There's lots of it in
> google.
> 
> -Michael.
> 
> 

There's a small difference here:

For a tray of size 12, with these lines:
xx---xxxxxxx
x--xxxxxxxxx
xxxxxxxx----

(x is a space)

In the case of bin packing, they can all sit together in the tray - the 
total length is less than 12. In this problem they can't, because two of 
them overlap.

Bin packing cares about totals, and tries to minimise the number of 
bins. But here totals don't tell the whole story. In fact, if every line 
starts at the same place and is of length 1, it doesn't really matter 
how large the tray is - you still have to stack them.

.