1 reply to this topic

[cicatrix1]

So it's been a while since I've done any serious programming besides the occasional admin script or the like, and I decided to get back into it and work on some exercises while teaching myself python.

I solved the box stacking problem listed here (problem #4):
http :// people.csail.mit.edu/bdean/6.046/dp/

but I do not think I did it efficiently at all.

Here's what I did:

* create a set of boxes, including duplicates of all boxes for all possible rotations (only taking non-redundant rotations by ensuring that length>width for any of the 3 possible heights)

* order the set based on area (greatest to least)

* run them all through a recursive function that checks if the next box can be stacked, adding it to the stack (and recording new height), and recursing back into the function for the next box.

This eventually goes through all possible combinations, checking only boxes smaller in area than the current top box (and does so starting with each box in the set). Once it's at the end of the stack it saves the stack and height if its the biggest and continues recursing until everything has been checked.

It's been a while since I studied big-O notation and I'm confused by it at this point, but I'm fairly sure my solution isn't O(n^2) as it's indicated in the problem that it should be.

For instance, in my made up sample of input boxes, 10 boxes (which grows up to max 30 with duplicates) takes around 100,000 checks to solve. There must be a more efficient way, right?

[WingedPanther]

Doing this recursively is a great way to get O(n!). Why not instead use a linked list and attempt to "sort" it to maximize height within the restrictions? Go for maximum possible height first, then start rotating boxes as needed to make it possible to fit them in using secondary or tertiary heights.