Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

RE: Packaging Algorithm

by marius (Hermit)
on Nov 07, 2000 at 08:50 UTC ( #40312=note: print w/ replies, xml ) Need Help??


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. =]


Comment on RE: Packaging Algorithm
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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://40312]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (12)
As of 2014-10-23 13:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (125 votes), past polls