Beefy Boxes and Bandwidth Generously Provided by pair Networks Bob
Syntactic Confectionery Delight
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

Okay, how many crate sizes can you buy at U-Haul? Or are you expecting him to buy sheet cardboard and build a custom crate in order to achieve maximal packing? The number of crate sizes to try is just a few. But then, I wouldn't try any sizes of crates at all!

Where did you get this crazy idea to try every possible origin for a package? If I put packages together tightly, then every package shares part of a side with another package. And we aren't talking about some theory trying to prove that we have the maximally tightest packing (which would be very hard, sure). Just assume that a reasonable packing exists where one package hits a corner of the crate (when was the last time you put packages in a crate in such a way that no package shared a corner with the crate?).

Now all you have to do is place a package in the corner of an infinite box (the positive octant) and add boxes in the resulting "corners". As you place boxes, keep track of the bounding crate. Iterate through all of the possibilities. Sure, this isn't trivial to code and the number of possiblities is huge. If you have a large number of packages, then try at random and report the best solution so far once you are tired of waiting. Who cares if it is brute force? Also, if you haven't placed all of the boxes yet and you are already worse off then your best solution so far, no need to continue adding packages.

Take N boxes.
First box: N choices (orientation doesn't matter yet)
Second box: N-1 boxes * <=3 corners * 6 orientations
Third box: N-2 boxes * <=5 corners * <=6 orientations
...

If I change the *3*5*7*9... terms to *4*6*8*10... then we are bounded by N! * 2^(N-1)*N! * 6^(N-1) == N!^2 * 12^(N-1). So assuming a worse-than-worst-possible case where we don't trim any chunks from the decision tree (we try all of the combinations in exactly the wrong order and don't eliminate overlapping boxes until we've placed all boxes), then we can still exhaustively search for 5 packages pretty quickly.

For 6 or 7, easy trimming of the decision tree might let you exhaustively search (hard to predict). For more than 7, you'd probably have to settle for stopping early and having a less optimal solution.

Brute force is often a very good way to solve real-life problems. That is why they computers that are fast. (:

        - tye (but my friends call me "Tye")

In reply to (tye)Re: Packaging Algorithm by tye
in thread Packaging Algorithm by marius

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others meditating upon the Monastery: (11)
    As of 2014-04-21 13:55 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      April first is:







      Results (495 votes), past polls