http://qs321.pair.com?node_id=40312


in reply to Packaging Algorithm

Incidentally, after much googling, I have found this which will almost cover what I'd like to do. After the suggestion of an IRC-"pal" I decided to limit myself to boxes readily available at U-Haul. The concept of limiting myself to purely integer units had already come to mind, and to come the number of "solutions" from being infinite, it's definitely needed. I'm not really looking for the definitive answer, just a good "guess" and close approximation. =]

Replies are listed 'Best First'.
RE: RE: Packaging Algorithm
by Fastolfe (Vicar) on Nov 07, 2000 at 09:03 UTC
    I've found a similar algorithm, written in C. This is giving me an excuse to play with the Inline module, but I won't have anything tonight. :)

    But yah the algorithm calls for a known container size, and it attempts to pack everything into that container. What I'd like to do is extend this C version using Perl to give us the needed "given these sizes, what's the smallest that successfully packs everything" behavior, which would just iterate from the smallest to the largest (or whatever order, since I guess some boxes of the same size might be cheaper than others, etc.), and return the first one that gets them all in.

    I thought about re-writing this totally in Perl, but the algorithm is rather complex.

      Well, I've got the perl part down to picking the box that has the next highest capacity volume as the total volume of sub-boxes. (I'm using box information available at U-Haul) Mind passing along the C algorithm?
        It's at home; I'll send you the URL I found then, but if you can't wait, I just did some searches on "box bin packing algorithm" and came up with a .c source that implements it.

        The problem with picking a box based on the total volume of your component boxes is that you can't expect to pack all of your boxes perfectly into a larger one. They're arbitrarily sized and you have to assume that there are going to be some gaps in and around them.