box stacking in graph theory

Please help me find a good solution for this problem.

We have n boxes with 3 dimen开发者_如何学JAVAsions. 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

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.

UPDATED (correct? but possibly not the most efficient):

Each box becomes 3 vertices (call these vertices related). Get a weighted DAG. Modify the algorithm described here Sort topologically (ignoring the fact that some vertices are related), follow the algorithm but instead of array of integers keep a list of the paths that lead to each vertex. Then when adding paths for a new vertex ('w' in wiki alg) make a list of paths that lead there by dropping the paths to v that contain a vertex related to w. Unlike the original algorithm, this one is exponential.

ORIGINAL WRONG ANSWER (see comments):

Each box becomes 3 nodes for its 3 surface sizes. Then create a directed graph connecting each surface to all surfaces of smaller sizes. Assign price to each edge to be equal to the 3rd dimension of the node (i.e. height) that the edge leads to. Now this is the problem of finding the longest path problem in a DAG.