box stacking in graph theory

Question

Please help me find a good solution for this problem.

We have n boxes with 3 dimensions. We can orient them and we want to put them on top of another to have a maximun height. We can put a box on top of an other box, if 2 dimensions (width and lenght) are lower than the dimensions of the box below.

For exapmle we have 3 dimensions w*D*h, we can show it in to (h*d,d*h,w*d,d*W,h*w,w*h) please help me to solve it in graph theory. in this problem we can not put(2*3)above(2*4) because it has the same width.so the 2 dimension shoud be smaller than the box

Answer 1

Edit: Only works if boxes can not be rotated about all axes.

If I understand the question correctly, it can be solved by dynamic programming. A simple algorithm finding the height of the maximum stack is:

Start by rotating all boxes such that for Box B_i, w_i <= d_i. This takes time O(n).

Now sort the boxes according to bottom area w_i * d_i and let the indexing show this. This takes time O(n log n).

Now B_i can be put onto B_j only if i < j, but i < j does not imply that B_i can be on B_j.

The largest stack with B_j on top is either

• B_j on the ground
• A stack made of the first j-1 boxes, with B_j on top.

Now we can create a recursive formula for computing the height of the maximum stack

H(j) = max (h_j, max (H(i)|i < j, d_i < d_j, w_i < w_j) + h_j)

and by computing max (H(j),i <= j <= n) we get the height of the maximum stack.

If we want the actual stack, we can attach some information to the H function and remember the indices.