Question:
Given a set of n types of Cuboid, find the maximum height that can be reached stacking instances of this Cuboid
Rules:
· A Cuboid can be stacked on top of another box only if the dimensions of the 2D base of the lower Cuboid are each strictly larger than those of the 2D base of the higher Cuboid.
· The Cuboid can be rotated so that any side functions as its base.
· It is allowable to use multiple instances of the same type of Cuboid.
Example:
n=3
dimensions(l,b,h)
Cuboid 1 - (1,2,3)
Cuboid 2 - (2,3,4)
Cuboid 3 - (3,4,5)
Expected result=15
(Stacking from top to bottom
1,2,3
2,3,4
3,4,5
4,5,3 height=3+4+5+3=15)
Solution:
Approach:
· initialize new array of boxes of length n*3 which will store all three rotations of box.
· sort the array in decreasing order of area of boxes
· initialize new array maxHeight of length n*3 which will store the max height achivable by having box i at the top
· now the problem is same as LIS with following optimal substructure property.
· maxHeight[i] = { Max ( maxHeight[j] ) + height(i) } where j < i and width(j) > width(i) and depth(j) > depth(i). If there is no such j then maxHeight[i] = height(i)
· Iterate through array maxHeight and return max element from it.
Java Program:
import java.util.*;
public class SolutionBoxStacking {
static class Box implements Comparable<Box>
{
int height, width, depth, area;
Box(int h, int w, int d)
{
this.height = h;
this.width = w;
this.depth = d;
this.area = width * depth;
}
//helper function to sort boxes according to their area
@Override
public int compareTo(Box b)
{
return b.area-this.area;
}
}
static int getMaxHeight(int n, Box[] arr)
{
//array to store all rotations of the boxes with original boxes
Box []boxes = new Box[n*3];
// generate all three rotations of the boxes
for(int i = 0;i<n;i++)
{
Box curr = arr[i];
boxes[i*3] = new Box(curr.height,Math.min(curr.width, curr.depth),Math.max(curr.width, curr.depth));
boxes[i*3 + 1] = new Box(curr.width, Math.min(curr.height, curr.depth), Math.max(curr.height, curr.depth));
boxes[i*3 + 2] = new Box(curr.depth, Math.min(curr.height, curr.width), Math.max(curr.height, curr.width));
}
Arrays.sort(boxes);
n *= 3;
//initialize array to store the achievable max height by having box i at the top of the stack
int maxHeight[] = new int[n];
for(int i = 0;i<n;i++) maxHeight[i] = boxes[i].height;
//iterate through all the boxes and update maxHeight using dp
for(int i = 0;i<n;i++)
{
Box curr = boxes[i];
int val = 0;
for(int j=0;j<i;j++)
{
Box temp = boxes[j];
if(temp.width > curr.width && temp.depth > curr.depth)
val = Math.max(val, maxHeight[j]);
}
maxHeight[i] += val;
}
//extract the max value from maxHeight and return
int max = -1;
for(int i = 0;i<n;i++) max = Math.max(max, maxHeight[i]);
return max;
}
public static void main(String[] args)
{
System.out.println("Enter the number of cubiod u have");
Scanner s = new Scanner(System.in);
int n = s.nextInt();
Box arr[] = new Box[n];
for(int i = 0;i<n;i++) {
System.out.println("Enter the length breath height of cubiod"+(i+1));
int h = s.nextInt();
int w = s.nextInt();
int d = s.nextInt();
arr[i] = new Box(h,w,d);
}
System.out.print("Maximum height:");
System.out.println(getMaxHeight(n, arr));
}
}
Output:
Enter the number of cubiod u have
4
Enter the length breath height of cubiod1
1
2
3
Enter the length breath height of cubiod2
2
3
4
Enter the length breath height of cubiod3
3
4
5
Enter the length breath height of cubiod4
4
5
6
Maximum height:22
