Box Stacking Problem

Stacking of boxes depending on their base

You have been given n different boxes. These boxes will have different heights, widths, and depths. You have to stack all these boxes in a manner such that the base surface area of upper box will not be greater than the base surface area of lower box. We can use different instances of a particular box.

Input:  {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32}

Output:  60

Concept behind this solution

When solving the problem, we have to remember some points like it is not necessary to find small base by only width and depth. By rotating the box, we can also get the small base area. Another thing is that we can use different instances of a particular box. It means, we can use different rotations of the same box for building the stack. So, we have to first make an array which will consist of all possible rotations of all boxes. After that, we will sort the array by base area. Now we can use dp and tabulation approach. See the code for further understanding.

Code:

// C++ program to get maximum height of box stack

#include<stdio.h>
#include<stdlib.h>
/* Constructing box */
struct Newbx
{
int h, w, d; 
};
int min (int x, int y)
{ return (x < y)? x : y; }
int max (int x, int y)
{ return (x > y)? x : y; }
int compare (const void *a, const void * b)
{
	return ( (*(Newbx *)b).d * (*(Newbx *)b).w ) -
		( (*(Newbx *)a).d * (*(Newbx *)a).w );
}
int maxStackHeight( Newbx arr[], int n )
{
Newbx rot[3*n];
int index = 0;
for (int i = 0; i < n; i++)
{
	rot[index].h = arr[i].h;
	rot[index].d = max(arr[i].d, arr[i].w);
	rot[index].w = min(arr[i].d, arr[i].w);
	index++;
	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++;
	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++;
}
n = 3*n;
qsort (rot, n, sizeof(rot[0]), compare);
int msh[n];
for (int i = 0; i < n; i++ )
	msh[i] = rot[i].h;
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;
		}


int max = -1;
for ( int i = 0; i < n; i++ )
	if ( max < msh[i] )
		max = msh[i];


return max;
}
int main()
{
Newbx arr[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} };
int n = sizeof(arr)/sizeof(arr[0]);


printf("The maximum possible height of stack is %d\n",
		maxStackHeight (arr, n) );


return 0;
}

// JAVA program to get maximum height of box stack

import java.util.*;


public class bn {
	
	/* Constructing box */
	static class Newbx implements Comparable<Newbx>{
	
		
		int h, w, d, area;
		
		public Newbx(int h, int w, int d) {
			this.h = h;
			this.w = w;
			this.d = d;
		}
		
		@Override
		public int compareTo(Newbx o) {
			return o.area-this.area;
		}
	}
	static int maxStackHeight( Newbx arr[], int n){
		
		Newbx[] rot = new Newbx[n*3];
		
		for(int i = 0;i < n;i++){
			Newbx newbx = arr[i];
			
			rot[3*i] = new Newbx(newbx.h, Math.max(newbx.w,newbx.d),
									Math.min(newbx.w,newbx.d));
			
			rot[3*i + 1] = new Newbx(newbx.w, Math.max(newbx.h,newbx.d),
									Math.min(newbx.h,newbx.d));
			
			rot[3*i + 2] = new Newbx(newbx.d, Math.max(newbx.w,newbx.h),
									Math.min(newbx.w,newbx.h));
		}
		
		
		for(int i = 0; i < rot.length; i++)
			rot[i].area = rot[i].w * rot[i].d;
		
		Arrays.sort(rot);
		
		int count = 3 * n;
		
		indexes
		msh[i] --> Maximum possible Stack Height
				with newbx i on top */
		int[]msh = new int[count];
		for (int i = 0; i < count; i++ )
			msh[i] = rot[i].h;
		
		for(int i = 0; i < count; i++){
			msh[i] = 0;
			Newbx newbx = rot[i];
			int val = 0;
			
			for(int j = 0; j < i; j++){
				Newbx prevNewbx = rot[j];
				if(newbx.w < prevNewbx.w && newbx.d < prevNewbx.d){
					val = Math.max(val, msh[j]);
				}
			}
			msh[i] = val + newbx.h;
		}
		
		int max = -1;
		
		for(int i = 0; i < count; i++){
			max = Math.max(max, msh[i]);
		}
		
		return max;
	}
	public static void main(String[] args) {
		
		Newbx[] arr = new Newbx[4];
		arr[0] = new Newbx(4, 6, 7);
		arr[1] = new Newbx(1, 2, 3);
		arr[2] = new Newbx(4, 5, 6);
		arr[3] = new Newbx(10, 12, 32);
		
		System.out.println("The maximum possible "+
						"height of stack is " +
						maxStackHeight(arr,4));
	}
}

# Python program to get maximum height of box stack

class Newbx:
	
	# Constructing newbx
	def __init__(self, h, w, d):
		self.h = h
		self.w = w
		self.d = d


	def __lt__(self, other):
		return self.d * self.w < other.d * other.w


def maxStackHeight(arr, n):
	rot = [Newbx(0, 0, 0) for _ in range(3 * n)]
	index = 0


	for i in range(n):
		rot[index].h = arr[i].h
		rot[index].d = max(arr[i].d, arr[i].w)
		rot[index].w = min(arr[i].d, arr[i].w)
		index += 1
		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 += 1
		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 += 1
	n *= 3
	rot.sort(reverse = True)


	msh = [0] * n


	for i in range(n):
		msh[i] = rot[i].h
	for i in range(1, n):
		for j in range(0, i):
			if (rot[i].w < rot[j].w and
				rot[i].d < rot[j].d):
				if msh[i] < msh[j] + rot[i].h:
					msh[i] = msh[j] + rot[i].h


	maxm = -1
	for i in range(n):
		maxm = max(maxm, msh[i])


	return maxm
if __name__ == "__main__":
	arr = [Newbx(4, 6, 7), Newbx(1, 2, 3),
		Newbx(4, 5, 6), Newbx(10, 12, 32)]
	n = len(arr)
	print("The maximum possible height of stack is",
		maxStackHeight(arr, n))

Output: