Math Is Fun Forum

lightnb

Guest

Exhaustive Algorithm to Fit N Cuboids in Another Cuboid

Hi,

I have a bunch of boxes (cuboids), each with a known X, Y, and Z dimension. I also have a larger cuboid with known X, Y and Z dimensions.

I need an algorithm to determine if all the small cuboids will fit in the larger one. I imagine this would require the program to try the cuboids in all possible combinations/orientations until all the small cuboids fit in the larger one, or until every possible orientation has been tried and failed.

Any ideas on where to start, or what the logic flow should be?

Testing if one box fits in another is easy... But once the first box is known to fit, where do you go from there?

Thanks in advance,

Nick

LQ

Real Member

Registered: 2006-12-04

Posts: 1,285

Re: Exhaustive Algorithm to Fit N Cuboids in Another Cuboid

First you divide the big box's X with the small box's X, the big box's Y with the small box's Y, the big box's Z with the small box's Z.
Then you eraze the decimals and multiply those answers.

Last edited by LQ (2008-08-18 20:29:15)

---

I see clearly now, the universe have the black dots, Thus I am on my way of inventing this remedy...

luca-deltodesco

Member

Registered: 2006-05-05

Posts: 1,470

Re: Exhaustive Algorithm to Fit N Cuboids in Another Cuboid

That will not work LQ, the problem is more complicated, simple example in 2D to show;

 _____5____
|          |   __3__
|          |  |_____1
4          |  
|__________|

with your method, you would have 5/3 -> 1. 4/1 -> 4.   1×4 = 4. however, you can fit 6.

 _________
|__1__| | | 
|__2__|5|6| 
|__3__|_|_| 
|__4__|___|

and in 3D this becomes even more evident, let's say the box was 4×5×3, and sub-box was 3×1×1, you method would say you can fit 15. but you can fit 20. with the second diagram above, where each of those 6 boxes are, you could fit the same pattern ontop of it twice over, and then in the unused space you could put 2 more boxes in orientated vertically to make 20

Last edited by luca-deltodesco (2008-08-18 21:34:30)

---

The Beginning Of All Things To End.
The End Of All Things To Come.

LQ

Real Member

Registered: 2006-12-04

Posts: 1,285

Re: Exhaustive Algorithm to Fit N Cuboids in Another Cuboid

X=Z=Y I thought. Elseways you keep the X rest, the Y rest and the Z rest, Xr,Yr and Zr
Then you continue doing what i showed in my first post, but replace X with Xr, Y with Yr and Z with Zr and add the answer to your first answer, then you continue doing that until no more boxes fit.

Perhaps you could do this also:
calculate the volume of the big box, sum up the smallest boxes and discard the ones with bigger lengths then the big box until you reach one box to many. throw away the biggest box.
1.Put in the smallest box first
2.Put the smallest of the hopefully inner boxes in the smallest corner, smallest side towards the smallest, medium towards medium, biggest side towards etc. etc. the biggest.
3.If the boxes don't fit, then exchange the rest with a box that does fit. If there is none, they will hardly fit. They couldn't possibly fit... Could they?

---

I see clearly now, the universe have the black dots, Thus I am on my way of inventing this remedy...