Box Stacking Problem

Problem:- 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.
Link to read


public class BoxStack {

    public static void main (String[] args) {
        //code
       //Let's suppose the example
        int [][] matrix={ {1,2,4},
                          {3,2,5}
                        };


        BoxStack  g=new BoxStack ();            
       
       //Generate all surfaces of the cuboid.
        int [][] finalMatrix=g.generateAllSurfaces( matrix);
     
        //Sort the cuboid based on surfaces, assumed the first two data is Width and depth, and third one
        //is height.

        g.sortMatrix(finalMatrix);
     
       //Now use augmented LIS to find the max sub sequence    
        g.findTheStackBox(finalMatrix);
 
    }
 
 
    public void findTheStackBox(int [][] matrix){
        int [] max = new int[matrix.length];   // to hold the max subsequences
        int [] result = new int[matrix.length]; //to hold the sequence
     
        for(int i=0;i<matrix.length;i++){
            max[i]=matrix[i][2];
            result[i]=i;
        }
 
        // writing LIS  
        for(int i=1,length=matrix.length;i<length;i++){
         
        for(int j=0;j<i;j++){
                //check for the surface validity
                if(matrix[i][0]< matrix[j][0] && matrix[i][1]< matrix[j][1]  ){
                max[i]=matrix[i][2]+max[j];
                    result[i]=j;
                }
            }
        }
   
        int index=0;
        int maxData=0;
        for(int i=0;i<max.length;i++){
            if(max[i]>maxData){
                maxData=max[i];
                index=i;
            }
         
         
        }
     
        System.out.println("Maximum Height of the stack is = "+maxData);
     
        //Now print the stack of the considered height top to bottom
     
        while(index!=result[index]){
         
            System.out.println(matrix[index][0]+" "+matrix[index][1]+" "+matrix[index][2]);
         
            index=result[index];
         
        }
        System.out.println(matrix[index][0]+" "+matrix[index][1]+" "+matrix[index][2]);
     
    }
 
    public void sortMatrix(int [][] matrix){
        for(int i=1,length=matrix.length;i<length;i++){
            int a=matrix[i][0];
            int b=matrix[i][1];
            int c=matrix[i][2];
            int pivot=a*b;
            int j=i-1;
 
            while(j>=0 && (matrix[j][0]*matrix[j][1])<=pivot){
                matrix[j+1][0]=matrix[j][0];
                matrix[j+1][1]=matrix[j][1];
                matrix[j+1][2]=matrix[j][2];
                j--;
            }
            matrix[j+1][0]=a;
            matrix[j+1][1]=b;
            matrix[j+1][2]=c;
        }
    }
 
 
    public int [][] generateAllSurfaces(int [][] matrix){
        int [][] temp = new int [3*matrix.length][3];
        int m=0;
     
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<3;j++){
                int a=matrix[i][j];
                int b=matrix[i][(j+1)%3];
                int c=matrix[i][(j+2)%3];
             
                if(b>c){
                    temp[m][0]=b;
                    temp[m][1]=c;
                }else{
                    temp[m][0]=c;
                    temp[m][1]=b;
                }
                temp[m][2]=a;
                m++;
            }
        }
     
     return temp;
    }
}