Subj : Re: stacking algorithm To : comp.programming From : Roger Willcocks Date : Sat Aug 06 2005 01:35 am "Michael Jørgensen" wrote in message news:42f3474d$0$683$edfadb0f@dread12.news.tele.dk... > > "Omri Barel" wrote in message > news:dcsp1h$jlq$1@reader-00.news.insnet.cw.net... >> Michael Jørgensen wrote: >> > "nobiscuit" 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. > > .