Subj : Re: stacking algorithm
To   : comp.programming
From : Michael Jørgensen
Date : Fri Aug 05 2005 02:02 pm


"Omri Barel" <spammer@b2z.com> wrote in message
news:dcsp1h$jlq$1@reader-00.news.insnet.cw.net...
> 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.

Yes, you're correct. I mistakenly thought I could move each line
horizontally, but that was explicitly forbidden in the OP.

-Michael.

.