Box stacking problem

I found this famous dp problem in many places, but I can not figure out how to solve.

You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.

This problem seems too complicated for me to figure out the steps. As it is 3D, I get three sequence of height, width开发者_JAVA技巧 and depth. But as it is possible to exchange 3 dimension the problem becomes more complicated for me. So please someone explain the steps to solve the problem when there is no swapping and then how to do it when swapping. I became tired about the problem. So please, please someone explain the solution easy way.

---

I think you can solve this using the dynamic programming longest increasing subsequence algorithm: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Accounting for the rotations is easy enough: for every tower all you have to check is what happens if you use its height as the length of the base and its width as the height and what happens if you use it in the natural way. For example:

=============
=           =
=           =
=           = L
=     H     =
=           =
=           =
=============   
      W

Becomes something like (yeah, I know it looks nothing like it should, just follow the notations):

==================
=                =
=                =  
=       W        = L
=                =
=                =
==================
        H

So for each block you actually have 3 blocks representing its possible rotations. Adjust your blocks array according to this, then sort by decreasing base area and just apply the DP LIS algorithm to the get the maximum height.

The adapted recurrence is: D[i] = maximum height we can obtain if the last tower must be i.

D[1] = h(1);
D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)

Answer is the max element of D.

See a video explaning this here: http://people.csail.mit.edu/bdean/6.046/dp/

---

The stack can be regarded as a sequence of x,y,z triplets (x,y being the 2D plane, and z the height), where x(i) > x(i+1) and y(i) > y(i+1). The goal is to maximize the sum of z picking the triplets from the set of available triplets - each triplet being one type of box in a particular orientation. It is pretty easy to see that enforcing the constraint x > y doesn't reduce the solution space. So each box generates 3 triplets, having each of w,h,d as the z coordinate.

If you regard the triplets as a directed acyclic graph where edges of length z exist between two triplets when the x,y constraints are satisfied between them, then the problem is of finding the longest path through that graph.

---

Let's first try to solve this problem in 2-D:

say you have rectangles with X's and Y's, and the question is similar (highest tower, but this time you only have to worry about one base dimension).
so first, you go over the whole collection, duplicating each rectangle by rotating it 90 degrees (swapping X and Y), except for squares (where X(1)=X(2) && Y(1)=Y(2)). this represents all possible variations.
then you sort them by their X side, from largest to smallest. in case of duplicate X value, you remove the one with the lower Y value.

same principle applied in the 3-D scenario, only now you DONT just multiply the collection's size by 6 (every possible variants of the W, H, D) but rather by 2. you do this by dismissing all variations where the width is lower than the depth ( so for each i, W(i)>=D(i)), and then dismissing the variation where the height is not the highest nor the lowest of the three dimensions (because the other two variations can go one on top of the other and this one can't join in). again, you also dismiss duplications (where W(1)=W(2) && H(1)=H(2) && D(1)=D(2)).
Then you should sort by width, only this time you don;t throw away variations with the same width (because one may fit in a tower that another may not) then you can use the LIS algorithm as described above by @IVlad :

D[1] = h(1);
D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists.

the trick was, you know that the width is the longest of the two, so you know the first element will not fit on top of any later element.

---

I suggest you create a tree (or some sort of tree structure) and parse it with depth search, calculating the max height from the individual vertical "height" (depening on rotation) values.

This (I think this is the basic approach).

Details over details:

The Tree root should be the floor, where any cube fits onto. From there you just create the child nodes of possible next (boxes that can be placed in a certain rotation ontop of the current box) boxes. Recursivly do that for each box and rotation.

When the tree is build, go through it and calc the total tower heigth from floor to a leaf of the tree.

---

A solution to the problem consists of three steps.

1. Sort dimensions for each box so that comparing any two boxes reduces to comparing their corresponding dimensions.
2. Sort the sequence of boxes lexicographically so that for each box, the boxes to the left are the boxes that may fit.
3. Apply the O(n^2) algorithm for the Longest Increasing Subsequence Problem.

The third step is the most expensive and bumps the complexity of the solution to O(n^2). If you would like to read a complete explanation of the approach, how each step contributes to finding an answer, and full code, have a look at the blog post I wrote about the problem.