Dynamic Programming | Set 22 (Box Stacking Problem) | GeeksforGeeks

Related: Stack of Boxes
Dynamic Programming | Set 22 (Box Stacking Problem) | GeeksforGeeks
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.

1) Generate all 3 rotations of all boxes. The size of rotation array becomes 3 times the size of original array. For simplicity, we consider depth as always smaller than or equal to width.

2) Sort the above generated 3n boxes in decreasing order of base area.

3) After sorting the boxes, the problem is same as LIS with following optimal substructure property.
MSH(i) = Maximum possible Stack Height with box i at top of stack
MSH(i) = { Max ( MSH(j) ) + height(i) } where j < i and width(j) > width(i) and depth(j) > depth(i).
If there is no such j then MSH(i) = height(i)

4) To get overall maximum height, we return max(MSH(i)) where 0 < i < n

int maxStackHeight( Box arr[], int n )

{

   /* Create an array of all rotations of given boxes

      For example, for a box {1, 2, 3}, we consider three

      instances{{1, 2, 3}, {2, 1, 3}, {3, 1, 2}} */

   Box rot[3*n];

   int index = 0;

   for (int i = 0; i < n; i++)

   {

      // Copy the original box

      rot[index] = arr[i];

      index++;

      // First rotation of box

      rot[index].h = arr[i].w;

      rot[index].d = max(arr[i].h, arr[i].d);

      rot[index].w = min(arr[i].h, arr[i].d);

      index++;

      // Second rotation of box

      rot[index].h = arr[i].d;

      rot[index].d = max(arr[i].h, arr[i].w);

      rot[index].w = min(arr[i].h, arr[i].w);

      index++;

   }

   // Now the number of boxes is 3n

   n = 3*n;

   /* Sort the array ‘rot[]‘ in decreasing order, using library

      function for quick sort */

   qsort (rot, n, sizeof(rot[0]), compare);

   // Uncomment following two lines to print all rotations

   // for (int i = 0; i < n; i++ )

   //    printf("%d x %d x %d\n", rot[i].h, rot[i].w, rot[i].d);

   /* Initialize msh values for all indexes

      msh[i] –> Maximum possible Stack Height with box i on top */

   int msh[n];

   for (int i = 0; i < n; i++ )

      msh[i] = rot[i].h;

   /* Compute optimized msh values in bottom up manner */

   for (int i = 1; i < n; i++ )

      for (int j = 0; j < i; j++ )

         if ( rot[i].w < rot[j].w &&

              rot[i].d < rot[j].d &&

              msh[i] < msh[j] + rot[i].h

            )

         {

              msh[i] = msh[j] + rot[i].h;

         }

   /* Pick maximum of all msh values */

   int max = -1;

   for ( int i = 0; i < n; i++ )

      if ( max < msh[i] )

         max = msh[i];

   return max;

}

Source: http://people.csail.mit.edu/bdean/6.046/dp/.
http://ideone.com/j2TklH
Prints the Box Stack too!!!
int compare(const void* a, const void* b)
{
    return ((*(Box *)b).l)*((*(Box *)b).w) - ((*(Box *)a).l)*((*(Box *)a).w);
}

int maxBoxHeight(Box arr[], int n)
{
    Box rot[3*n];
    int temp;
    int r=0;

    for(int i=0; i<n; i++)
    {
        rot[r] = arr[i];
        r++;

        rot[r].h = arr[i].l;
        rot[r].l = max(arr[i].w, arr[i].h);
        rot[r].w = min(arr[i].w, arr[i].h);
        r++;

        rot[r].h = arr[i].w;
        rot[r].l = max(arr[i].l, arr[i].h);
        rot[r].w = min(arr[i].l, arr[i].h);
        r++;
    }

    n = 3*n;
    qsort(rot, n, sizeof(rot[0]), compare);

    int tab[n];
    int res[n];

    for(int i=0; i<n; i++)
        tab[i] = rot[i].h, res[i] = -1;

    for(int i=1; i<n; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(rot[i].l < rot[j].l && rot[i].w < rot[j].w && tab[j] + rot[i].h > tab[i])
            {
                tab[i] = tab[j] + rot[i].h;
                res[i] = j;
            }
        }
    }

    int k=n-1;
    while(k != -1)
    {
        printf("%2d x %2d x %2d\n", rot[k].l, rot[k].w, rot[k].h);
        k = res[k];
    }

    return tab[n-1];

}
Crack Coding Interview: [CC150v5] 9.10 Stack Up the Boxes
A little bit different
http://www.shuatiblog.com/blog/2014/09/17/stack-up-boxes/
You have a stack of n boxes, with widths w., heights h, and depths d. The boxes can only be stacked on top of one another if each box is strictly larger than the box above it in width, height, and depth.

Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box.

Because here it requires strictly larger => so we don't need do backtrack: remove it from box arrays then add back later.
http://www.shuatiblog.com/blog/2014/09/17/stack-up-boxes/
we keeps 2 DP arrays

public static ArrayList<Box> createStack(Box[] boxes) {
    ArrayList<Box> ans = new ArrayList<Box>();
    int len = boxes.length;
    int[] heights = new int[len];
    int[] preMap = new int[len];
    int maxIndex = 0;

    // start DP
    for (int i = 0; i < len; i++) {
        heights[i] = boxes[i].height;
        preMap[i] = -1;
        for (int j = 0; j < i; j++) {
            if (boxes[j].canBeAbove(boxes[i])) {
                int newHeight = heights[j] + boxes[i].height;
                if (newHeight > heights[i]) {
                    heights[i] = newHeight;
                    preMap[i] = j;
                }
            }
        }
        // now updated maxIndex
        if (heights[i] > heights[maxIndex]) {
            maxIndex = i;
        }
    }

    // print from maxIndex all the way backwards
    while (maxIndex != -1) {
        ans.add(boxes[maxIndex]);
        // the print order is reversed, so...
        maxIndex = preMap[maxIndex];
    }
    return ans;
}

http://www.cnblogs.com/grandyang/p/4847695.html
我们也可以用哈希表来优化，保存我们之前算过的最优解，那么在递归调用需要相同的结果时，就可以直接从哈希表中调用
https://github.com/wzhishen/cracking-the-coding-interview/blob/master/src/chap09/Q10.java
//    You have a stack of n boxes, with widths w, heights h and depths d. The boxes
//    cannot be rotated and can only be stacked on top of one another if each box in the
//    stack is strictly larger than the box above it in width, height, and depth. Implement
//    a method to build the tallest stack possible, where the height of a stack is the sum of
//    the heights of each box.
static ArrayList<Box> buildTallestStack(ArrayList<Box> boxes, Box bottom) {
    ArrayList<Box> maxStack = null;
    int maxHeight = 0;
    for (Box b : boxes) {
        if (b.canPlaceAbove(bottom)) {
            ArrayList<Box> newStack = buildTallestStack(boxes, b);
            int newHeight = stackHeight(newStack);
            if (newHeight > maxHeight) {
                maxHeight = newHeight;
                maxStack = newStack;
            }
        }
    }
    if (maxStack == null) maxStack = new ArrayList<Box>();
    if (bottom != null) maxStack.add(0, bottom);
    return maxStack;
}

static ArrayList<Box> buildTallestStack(ArrayList<Box> boxes) {
    if (boxes == null) return null;
    return buildTallestStack(boxes, null);
}

static ArrayList<Box> buildTallestStackDP(ArrayList<Box> boxes, Box bottom, 
        HashMap<Box, ArrayList<Box>> cache) {
    if (cache.containsKey(bottom))
        return cache.get(bottom);
    
    ArrayList<Box> maxStack = null;
    int maxHeight = 0;
    for (Box b : boxes) {
        if (b.canPlaceAbove(bottom)) {
            ArrayList<Box> newStack = buildTallestStackDP(boxes, b, cache);
            int newHeight = stackHeight(newStack);
            if (newHeight > maxHeight) {
                maxHeight = newHeight;
                maxStack = newStack;
            }
        }
    }
    if (maxStack == null) maxStack = new ArrayList<Box>();
    if (bottom != null) maxStack.add(0, bottom);
    cache.put(bottom, maxStack);
    return maxStack;
}

static ArrayList<Box> buildTallestStackDP(ArrayList<Box> boxes) {
    if (boxes == null) return null;
    return buildTallestStackDP(boxes, null, new HashMap<Box, ArrayList<Box>>());
}
private static int stackHeight(ArrayList<Box> boxes) {
    int height = 0;
    for (Box b : boxes) {
        height += b.height;
    }
    return height;
}

static class Box {
    int width; int length; int height;
    public Box(int w, int l, int h) {width=w;length=l;height=h;}
    
    boolean canPlaceAbove(Box b) {
        return b == null ||
                (this.width < b.width &&
                this.length < b.length &&
                this.height < b.height);
    }

}
https://ziliangzhu.wordpress.com/2013/11/16/you-have-a-stack-of-n-boxes-with-widths-w-heights-l-and-depths-dr-the-boxes-cannot-be-rotated-and-can-only-be-stacked-on-top-of-one-another-if-each-box-in-the-stack-is-strictly-larger-than-the-bo/
public ArrayList<Box> getTallestBoxStack(Box[] boxes) {
 HashMap<Box, ArrayList<Box>> myHash = new HashMap<Box, ArrayList<Box>>();
 return getTallestBoxStack(myHash, boxes, null);
 }

private ArrayList<Box> getTallestBoxStack(
 HashMap<Box, ArrayList<Box>> myHash, Box[] boxes, Box currentBox) {
// Base and Recursion
// Check hashmap
if (currentBox != null && myHash.containsKey(currentBox)) {
return myHash.get(currentBox);
} else {
// Temporary instance
ArrayList<Box> previous = null;
double previousHighestHeight = 0;

// To return value
ArrayList<Box> previousFinal = new ArrayList<Box>();

// Recursion
for (int i = 0; i < boxes.length; i++) {
// If any box is smaller than current box
if (boxes[i].isSmallerThan(currentBox)) {
previous = getTallestBoxStack(myHash, boxes, boxes[i]);
// Compare height and update the final previous
double previousHeight = getStackHeight(previous);
if (previousHeight > previousHighestHeight) {
// update height record
previousHighestHeight = previousHeight;
previousFinal = previous;
}
}
}

// Ready to return
if (currentBox != null){
previousFinal.add(currentBox);
// update hashmap
myHash.put(currentBox, previousFinal);
}

// return a deep copy
return new ArrayList<Box>(previousFinal);
}
 }

private double getStackHeight(ArrayList<Box> boxes) {
 double returnVal = 0;
 for (Box i : boxes) {
 returnVal += i.height;
 }
 return returnVal;
 }
}
https://richdalgo.wordpress.com/2014/12/31/cc150-recursion-and-dp/
https://gist.github.com/ivycheung1208/9b0c648aacdb1d52ae11
http://codinginterview.net/post/you-have-a-stack-of-n-boxes-with-widths-w-heights-h-and-depths-d-implement-a-method-to-build-the-tallest-stack-possible
Understanding k-Dimensions
You are given n boxes each of k dimensions to figure out the maximum number of box-in-box chains (called nested boxes) you can form.

For a box to fit, the value of every dimension must be smaller than the pair-wise association of the other box. What his means is box (1,2,3) fits into box (2,3,4) because each dimension is 1 unit smaller. To easily determine this, we can simply sort the box's dimensions and compare each value pairwise. Now we can define the box object.

Given n boxes with length and width. A box with smaller length and smaller width can be put on a box with larger length and larger width.
Each box height is 1. Find the tallest box that they can put together. In general, we can build the box with m-dimension.
For example, if we have:
boxes = {
{0, 0},
{1, 2},
{1, 1},
{3, 4},
{4, 3},
{4, 4},
{3, 3} };
A longest possible combination is: (4, 4)->(3, 4)->(3, 3)->(1, 2)->(1, 1)->(0, 0). So tallest height is 6.

For n boxes, we do comparison between each box. If box[j] can be put on box[i], then we put an edge from box[i]->box[j].
In this way, we build a graph among boxes. Gathering all the boxes which doesn’t has parent, we use BFS to iterate.
The max number of iteration will be the result.

Assume a graph is like below, we can see the total iteration starting from v1, v2 to the end is 4.

public static int getTallestBox(int[][] boxes) {

    assert boxes!=null && boxes.length>0 && boxes[0]!=null && boxes[0].length>0;

    Queue<Node> mainQueue = initialStack(boxes);

    Queue<Node> auxQueue = new ArrayDeque<Node>();

    int tall = 0;

    while(!mainQueue.isEmpty()) {

        tall++;

        while (!mainQueue.isEmpty()) {

            Node node = mainQueue.remove();

            for(Node curr:node.neighbor) {

                auxQueue.add(curr);

            }

        }

        Queue<Node> tmp = mainQueue;

        mainQueue = auxQueue;

        auxQueue = tmp;

    }

    return tall;

}

public static Queue<Node> initialStack(int[][] boxes) {

    boolean[] nonHeads = new boolean[boxes.length];

    Node[] nodes = new Node[boxes.length];

    Queue<Node> heads = new ArrayDeque<Node>();

    for(int i=0; i<nodes.length; i++) {

        nodes[i] = new Node(boxes[i]);

    }

    // build graph

    for(int i=0; i<nodes.length-1; i++) {

        for(int j=i+1; j<nodes.length; j++) {

            int compare = compare(nodes[i].box, nodes[j].box);

            switch (compare) {

                case -1:

                    nodes[j].addNeighbor(nodes[i]);

                    nonHeads[i] = true;

                    break;

                case 1:

                    nodes[i].addNeighbor(nodes[j]);

                    nonHeads[j] = true;

                    break;

                case 0:

                    break;

            }// switch

        }// for

    }

    // mark head nodes who has out-going edge.

    for(int i=0; i<nonHeads.length; i++) {

        if (!nonHeads[i])

            heads.add(nodes[i]);

    }

    return heads;

}

/*

Return 1 when arr1>arr2.

Return -1 when arr1<arr2.

Return 0 when arr1 can't compare to arr2.

 */

public static int compare(int[] arr1, int[] arr2) {

    boolean larger = true;

    boolean smaller = true;

    for(int i=0; i<arr1.length; i++) {

        if(arr1[i]<arr2[i])

            larger = false;

        else if(arr1[i]>arr2[i])

            smaller = false;

        else if(!larger && !smaller)

            return 0;

    }

    if(larger)

        return 1;

    else if(smaller)

        return -1;

    return 0;

}

public static class Node {

    public int[] box;

    public HashSet<Node> neighbor = new HashSet<Node>();

    public Node(int[] box) {

        this.box = box;

    }

    public void addNeighbor(Node node) {

        neighbor.add(node);

    }

}

public static void main(String[] args) {

    int[] arr1 = {1, 4, 5};

    int[] arr2 = {1, 3, 5};

    int[][] boxes = {

            {0, 0},

            {1, 2},

            {1, 1},

            {3, 4},

            {4, 3},

            {4, 4},

            {3, 3}

    };

    System.out.println(getTallestBox(boxes));

}

Read full article from Dynamic Programming | Set 22 (Box Stacking Problem) | GeeksforGeeks