Data Modelling & AI Data Structure & Algorithm

Box Stacking Problem | DP-22

20 June 2025

0

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.
Source: http://people.csail.mit.edu/bdean/6.046/dp/. The link also has a video for an explanation of the solution.

The Box Stacking problem is a variation of LIS problem. We need to build a maximum height stack.
Following are the key points to note in the problem statement:
1) A box can be placed on top of another box only if both width and depth of the upper placed box are smaller than width and depth of the lower box respectively.
2) We can rotate boxes such that width is smaller than depth. For example, if there is a box with dimensions {1x2x3} where 1 is height, 2×3 is base, then there can be three possibilities, {1x2x3}, {2x1x3} and {3x1x2}
3) We can use multiple instances of boxes. What it means is, we can have two different rotations of a box as part of our maximum height stack.
Following is the solution based on DP solution of LIS problem.

Method 1 : dynamic programming using tabulation

1) Generate all 3 rotations of all boxes. The size of rotation array becomes 3 times the size of the original array. For simplicity, we consider width as always smaller than or equal to depth.
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
Following is the implementation of the above solution.

C++

/* Dynamic Programming implementation of Box Stacking problem */
#include<stdio.h>
#include<stdlib.h>
 
/* Representation of a box */
struct Box
{
  // h --> height, w --> width, d --> depth
  int h, w, d;  // for simplicity of solution, always keep w <= d
};
 
// A utility function to get minimum of two integers
int min (int x, int y)
{ return (x < y)? x : y; }
 
// A utility function to get maximum of two integers
int max (int x, int y)
{ return (x > y)? x : y; }
 
/* Following function is needed for library function qsort(). We
   use qsort() to sort boxes in decreasing order of base area. 
   Refer following link for help of qsort() and compare()
   http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
int compare (const void *a, const void * b)
{
    return ( (*(Box *)b).d * (*(Box *)b).w ) -
           ( (*(Box *)a).d * (*(Box *)a).w );
}
 
/* Returns the height of the tallest stack that can be
   formed with give type of boxes */
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].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++;
 
      // 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 non-increasing order
      of base area */
   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;
}
 
/* Driver program to test above function */
int main()
{
  Box 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

/* Dynamic Programming implementation 
of Box Stacking problem in Java*/
import java.util.*;
 
public class GFG {
     
    /* Representation of a box */
    static class Box implements Comparable<Box>{
     
        // h --> height, w --> width,
        // d --> depth
        int h, w, d, area;
         
        // for simplicity of solution,
        // always keep w <= d
 
        /*Constructor to initialise object*/
        public Box(int h, int w, int d) {
            this.h = h;
            this.w = w;
            this.d = d;
        }
         
        /*To sort the box array on the basis
        of area in decreasing order of area */
        @Override
        public int compareTo(Box o) {
            return o.area-this.area;
        }
    }
 
    /* Returns the height of the tallest
    stack that can be formed with give 
    type of boxes */
    static int maxStackHeight( Box arr[], int n){
         
        Box[] rot = new Box[n*3];
         
        /* New Array of boxes is created - 
        considering all 3 possible rotations, 
        with width always greater than equal
        to width */
        for(int i = 0;i < n;i++){
            Box box = arr[i];
             
            /* Original Box*/
            rot[3*i] = new Box(box.h, Math.max(box.w,box.d), 
                                    Math.min(box.w,box.d));
             
            /* First rotation of box*/
            rot[3*i + 1] = new Box(box.w, Math.max(box.h,box.d), 
                                       Math.min(box.h,box.d));
             
            /* Second rotation of box*/
            rot[3*i + 2] = new Box(box.d, Math.max(box.w,box.h),
                                       Math.min(box.w,box.h));
        }
         
        /* Calculating base area of 
        each of the boxes.*/
        for(int i = 0; i < rot.length; i++)
            rot[i].area = rot[i].w * rot[i].d;
         
        /* Sorting the Boxes on the basis 
        of Area in non Increasing order.*/
        Arrays.sort(rot);
         
        int count = 3 * n;
         
        /* Initialize msh values for all 
        indexes 
        msh[i] --> Maximum possible Stack Height
                   with box i on top */
        int[]msh = new int[count];
        for (int i = 0; i < count; i++ )
            msh[i] = rot[i].h;
         
        /* Computing optimized msh[] 
        values in bottom up manner */
        for(int i = 0; i < count; i++){
            msh[i] = 0;
            Box box = rot[i];
            int val = 0;
             
            for(int j = 0; j < i; j++){
                Box prevBox = rot[j];
                if(box.w < prevBox.w && box.d < prevBox.d){
                    val = Math.max(val, msh[j]);
                }
            }
            msh[i] = val + box.h;
        }
         
        int max = -1;
         
        /* Pick maximum of all msh values */
        for(int i = 0; i < count; i++){
            max = Math.max(max, msh[i]);
        }
         
        return max;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args) {
         
        Box[] arr = new Box[4];
        arr[0] = new Box(4, 6, 7);
        arr[1] = new Box(1, 2, 3);
        arr[2] = new Box(4, 5, 6);
        arr[3] = new Box(10, 12, 32);
         
        System.out.println("The maximum possible "+
                           "height of stack is " + 
                           maxStackHeight(arr,4));
    }
}
 
// This code is contributed by Divyam 

Python3

# Dynamic Programming implementation
# of Box Stacking problem
class Box:
     
    # Representation of a box
    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):
 
    # 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}}
    rot = [Box(0, 0, 0) for _ in range(3 * n)]
    index = 0
 
    for i in range(n):
 
        # Copy the original box
        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
 
        # First rotation of the 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 += 1
 
        # Second rotation of the 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 += 1
 
    # Now the number of boxes is 3n
    n *= 3
 
    # Sort the array 'rot[]' in non-increasing 
    # order of base area
    rot.sort(reverse = True)
 
    # Uncomment following two lines to print 
    # all rotations 
    # for i in range(n):
    #     print(rot[i].h, 'x', rot[i].w, 'x', rot[i].d)
 
    # Initialize msh values for all indexes
    # msh[i] --> Maximum possible Stack Height 
    # with box i on top
    msh = [0] * n
 
    for i in range(n):
        msh[i] = rot[i].h
 
    # Compute optimized msh values
    # in bottom up manner
    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
 
# Driver Code
if __name__ == "__main__":
    arr = [Box(4, 6, 7), Box(1, 2, 3),
           Box(4, 5, 6), Box(10, 12, 32)]
    n = len(arr)
    print("The maximum possible height of stack is",
           maxStackHeight(arr, n))
 
# This code is contributed by vibhu4agarwal

C#

using System;
 
class Box
{
    public int h, w, d, area;
    public Box(int h, int w, int d)
    {
        this.h = h;
        this.w = w;
        this.d = d;
    }
 
    public bool IsSmallerThan(Box other)
    {
        return this.w * this.d < other.w * other.d;
    }
}
 
class GFG
{
    public static 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 = new Box[3 * n];
 
        for (int i = 0; i < n; i++)
        {
            Box box = arr[i];
            // Copy the original box
            rot[3 * i] = new Box(box.h, Math.Max(box.w, box.d), Math.Min(box.w, box.d));
 
            // First rotation of the box
            rot[3 * i + 1] = new Box(box.w, Math.Max(box.h, box.d), Math.Min(box.h, box.d));
 
            // Second rotation of the box
            rot[3 * i + 2] = new Box(box.d, Math.Max(box.w, box.h), Math.Min(box.h, box.w));
        }
 
        // Calculating base area ofeach of the boxes
        for (int i = 0; i < 3*n; i++)
            rot[i].area = rot[i].w * rot[i].d;
 
        // Sort the array 'rot[]' in non-increasing
        // order of base area
        Array.Sort(rot, (a, b) => b.IsSmallerThan(a) ? -1 : 1);
 
        int count = 3 * n;
 
        // Initialize msh values for all indexes
        // msh[i] --> Maximum possible Stack Height
        // with box i on top
        int[] msh = new int[count];
 
        for (int i = 0; i < count; i++)
            msh[i] = rot[i].h;
 
        // Compute optimized msh values
        // in bottom up manner
        for (int i = 0; i < count; i++)
        {
            msh[i] = 0;
            Box box = rot[i];
            int val = 0;
 
            for (int j = 0; j < i; j++)
            {
                Box prevBox = rot[j];
                if (box.w < prevBox.w && box.d < prevBox.d)
                {
                    val = Math.Max(val, msh[j]);
                }
            }
            msh[i] = val + box.h;
        }
 
        int max = -1;
        for (int i = 0; i < count; i++)
        {
            max = Math.Max(max, msh[i]);
        }
 
        return max;
    }
 
    public static void Main()
    {
        Box[] arr = new Box[4];
        arr[0] = new Box(4, 6, 7);
        arr[1] = new Box(1, 2, 3);
        arr[2] = new Box(4, 5, 6);
        arr[3] = new Box(10, 12, 32);
 
        Console.WriteLine("The maximum possible " + "height of stack is " + MaxStackHeight(arr, 4));
    }
}

Javascript

// Definition of a Box
class Box {
  constructor(h, w, d) {
    this.h = h; // height
    this.w = w; // width
    this.d = d; // depth
  }
}
 
// Utility function to get the minimum of two integers
function min(a, b) {
  return a < b ? a : b;
}
 
// Utility function to get the maximum of two integers
function max(a, b) {
  return a > b ? a : b;
}
 
// Function to compare two boxes based on their base area
function compare(box1, box2) {
  return box2.w * box2.d - box1.w * box1.d;
}
 
// Function to find the maximum height of a stack of boxes
function maxStackHeight(boxes) {
  // Create an array of all rotations of the boxes
  const rotations = [];
  for (let i = 0; i < boxes.length; i++) {
    const box = boxes[i];
    // Original orientation
    rotations.push(new Box(box.h, max(box.w, box.d), min(box.w, box.d)));
    // First rotation
    rotations.push(new Box(box.w, max(box.h, box.d), min(box.h, box.d)));
    // Second rotation
    rotations.push(new Box(box.d, max(box.h, box.w), min(box.h, box.w)));
  }
 
  // Sort the rotations in non-increasing order of their base area
  rotations.sort(compare);
 
  // Initialize an array to store the maximum stack height for each box
  const maxStackHeight = new Array(rotations.length).fill(0);
  for (let i = 0; i < rotations.length; i++) {
    maxStackHeight[i] = rotations[i].h;
  }
 
  // Compute the maximum stack height for each box in bottom-up manner
  for (let i = 1; i < rotations.length; i++) {
    for (let j = 0; j < i; j++) {
      if (rotations[i].w < rotations[j].w && rotations[i].d < rotations[j].d) {
        maxStackHeight[i] = max(maxStackHeight[i], maxStackHeight[j] + rotations[i].h);
      }
    }
  }
 
  // Find the maximum stack height
  let maxHeight = 0;
  for (let i = 0; i < rotations.length; i++) {
    if (maxHeight < maxStackHeight[i]) {
      maxHeight = maxStackHeight[i];
    }
  }
 
  return maxHeight;
}
 
// Example usage
const boxes = [
  new Box(4, 6, 7),
  new Box(1, 2, 3),
  new Box(4, 5, 6),
  new Box(10, 12, 32),
];
const ans = maxStackHeight(boxes);
console.log(ans); // Output: 60

Output

The maximum possible height of stack is 60

In the above program, given input boxes are {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32}. Following are all rotations of the boxes in decreasing order of base area.

   10 x 12 x 32
   12 x 10 x 32
   32 x 10 x 12
   4 x 6 x 7
   4 x 5 x 6
   6 x 4 x 7
   5 x 4 x 6
   7 x 4 x 6
   6 x 4 x 5
   1 x 2 x 3
   2 x 1 x 3
   3 x 1 x 2

The height 60 is obtained by boxes { {3, 1, 2}, {1, 2, 3}, {6, 4, 5}, {4, 5, 6}, {4, 6, 7}, {32, 10, 12}, {10, 12, 32}}
Time Complexity: O(n^2)
Auxiliary Space: O(n), since n extra space has been taken.

Method 2 : dynamic programming using memoization (top-down)

C++

/* Dynamic Programming top-down implementation of Box
 * Stacking problem */
#include <bits/stdc++.h>
using namespace std;
 
/* Representation of a box */
class Box {
public:
    int length;
    int width;
    int height;
};
 
// dp array
int dp[303];
 
/*
    boxes -> vector of Box
    bottom_box_index -> index of the bottom box
    index -> index of current box
*/
/* NOTE: we can use only one variable in place of bottom_box_index and index
     but it has been avoided to make it simple */
int findMaxHeight(vector<Box>& boxes, int bottom_box_index, int index)
{
 
    // base case
    if (index < 0)
        return 0;
 
    if (dp[index] != -1)
        return dp[index];
 
    int maximumHeight = 0;
 
    // recurse
    for (int i = index; i >= 0; i--) {
 
        // if there is no bottom box
        if (bottom_box_index == -1
 
            // or if length & width of new box is < that of
            // bottom box
            || (boxes[i].length
                    < boxes[bottom_box_index].length
                && boxes[i].width
                       < boxes[bottom_box_index].width))
 
            maximumHeight
                = max(maximumHeight,
                      findMaxHeight(boxes, i, i - 1)
                          + boxes[i].height);
    }
 
    return dp[index] = maximumHeight;
}
 
/* wrapper function for recursive calls which
Returns the height of the tallest stack that can be
formed with give type of boxes */
int maxStackHeight(int height[], int width[], int length[],
                   int types)
{
    // creating a vector of type Box class
    vector<Box> boxes;
 
    // Initialize dp array with -1
    memset(dp, -1, sizeof(dp));
 
    Box box;
 
    /* 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}} */
    for (int i = 0; i < types; i++) {
 
        // copy original box
        box.height = height[i];
        box.length = max(length[i], width[i]);
        box.width = min(length[i], width[i]);
 
        boxes.push_back(box);
 
        // First rotation of box
        box.height = width[i];
        box.length = max(length[i], height[i]);
        box.width = min(length[i], height[i]);
 
        boxes.push_back(box);
 
        // Second rotation of box
        box.height = length[i];
        box.length = max(width[i], height[i]);
        box.width = min(width[i], height[i]);
 
        boxes.push_back(box);
    }
 
    // sort by area in ascending order .. because we will be dealing with this vector in reverse
    sort(boxes.begin(), boxes.end(), [](Box b1, Box b2) {
        // if area of box1 < area of box2
        return (b1.length * b1.width)
               < (b2.length * b2.width);
    });
   
   // Uncomment following two lines to print all rotations
    //for (int i = boxes.size() - 1; i >= 0; i-- )
   //   printf("%d x %d x %d\n", boxes[i].length, boxes[i].width, boxes[i].height);
 
    return findMaxHeight(boxes, -1, boxes.size() - 1);
}
 
int main()
{
 
    // where length, width and height of a particular box
    // are at ith index of the following arrays
    int length[] = { 4, 1, 4, 10 };
    int width[] = { 6, 2, 5, 12 };
    int height[] = { 7, 3, 6, 32 };
 
    int n = sizeof(length) / sizeof(length[0]);
 
    printf("The maximum possible height of stack is %d\n",
           maxStackHeight(height, length, width, n));
 
    return 0;
}

Java

import java.util.Arrays;
 
public class BoxStacking {
    static class Box implements Comparable<Box> {
        int length;
        int width;
        int height;
 
        public Box(int length, int width, int height) {
            this.length = length;
            this.width = width;
            this.height = height;
        }
 
        public int compareTo(Box b) {
            return Integer.compare(this.length * this.width, b.length * b.width);
        }
    }
 
    public static int maxStackHeight(int[] length, int[] width, int[] height) {
        int n = length.length;
        Box[] boxes = new Box[3 * n];
 
        int k = 0;
        for (int i = 0; i < n; i++) {
            boxes[k++] = new Box(length[i], width[i], height[i]);
            boxes[k++] = new Box(width[i], height[i], length[i]);
            boxes[k++] = new Box(height[i], length[i], width[i]);
        }
 
        Arrays.sort(boxes);
 
        int[] dp = new int[3 * n];
        int maxHeight = 0;
 
        for (int i = k - 1; i >= 0; i--) {
            dp[i] = boxes[i].height;
            for (int j = i + 1; j < k; j++) {
                if (boxes[i].length < boxes[j].length
                        && boxes[i].width < boxes[j].width) {
                    dp[i] = Math.max(dp[i], boxes[i].height + dp[j]);
                }
            }
 
            maxHeight = Math.max(maxHeight, dp[i]);
        }
 
        return maxHeight;
    }
 
    public static void main(String[] args) {
        int[] length = { 4, 1, 4, 10 };
        int[] width = { 6, 2, 5, 12 };
        int[] height = { 7, 3, 6, 32 };
 
        System.out.println("The maximum possible height of stack is "
                + maxStackHeight(length, width, height));
    }
}
// This code contributed SRJ

Python3

# Dynamic Programming top-down implementation of Box
# Stacking problem
 
class Box:
    def __init__(self, length, width, height):
        self.length = length
        self.width = width
        self.height = height
 
# dp array
dp = [-1]*303
 
def findMaxHeight(boxes, bottom_box_index, index):
 
    # base case
    if index < 0:
        return 0
 
    if dp[index] != -1:
        return dp[index]
 
    maximumHeight = 0
 
    # recurse
    for i in range(index, -1, -1):
 
        # if there is no bottom box
        if bottom_box_index == -1 or (boxes[i].length < boxes[bottom_box_index].length 
            and boxes[i].width < boxes[bottom_box_index].width):
 
            maximumHeight = max(maximumHeight, findMaxHeight(boxes, i, i-1) + boxes[i].height)
 
    dp[index] = maximumHeight
    return maximumHeight
 
# Returns the height of the tallest stack that can be
# formed with give type of boxes 
def maxStackHeight(height, width, length, types):
 
    # creating a vector of type Box class
    boxes = []
 
    # Initialize dp array with -1
    dp[:] = [-1]*303
 
    # 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}}
    for i in range(types):
 
        # copy original box
        box = Box(length[i], max(length[i], width[i]), min(length[i], width[i]))
        boxes.append(box)
 
        # First rotation of box
        box = Box(width[i], max(length[i], height[i]), min(length[i], height[i]))
        boxes.append(box)
 
        # Second rotation of box
        box = Box(length[i], max(width[i], height[i]), min(width[i], height[i]))
        boxes.append(box)
 
    # sort by area in ascending order .. because we will be dealing with this vector in reverse
    boxes.sort(key=lambda box : (box.length * box.width))
 
    # Uncomment following two lines to print all rotations
    #for (int i = boxes.size() - 1; i >= 0; i-- )
    #   printf("%d x %d x %d\n", boxes[i].length, boxes[i].width, boxes[i].height);
 
    return findMaxHeight(boxes, -1, len(boxes)-1)
 
# where length, width and height of a particular box
# are at ith index of the following arrays
length = [ 4, 1, 4, 10 ]
width = [ 6, 2, 5, 12 ]
height = [ 7, 3, 6, 32 ]
 
types = len(length)
 
print("The maximum possible height of stack is", maxStackHeight(height, length, width, types))
 
# This code is contributed b factworx412

Javascript

class Box {
       constructor(length, width, height) {
         this.length = length;
         this.width = width;
         this.height = height;
       }
     }
 
     function maxStackHeight(ength, width, height) {
       let n = length.length;
       let boxes = new Array();
       let k = 0;
       for (let i = 0; i < n; i++) {
         boxes[k++] = new Box(length[i], width[i], height[i]);
         boxes[k++] = new Box(width[i], height[i], length[i]);
         boxes[k++] = new Box(height[i], length[i], width[i]);
       }
 
       boxes.sort((b1, b2) => {
         // if area of box1 < area of box2
         return b1.length * b1.width - b2.length * b2.width;
       });
 
       let dp = new Array(3 * n);
       let maxHeight = 0;
 
       for (let i = k - 1; i >= 0; i--) {
         dp[i] = boxes[i].height;
         for (let j = i + 1; j < k; j++) {
           if (
             boxes[i].length < boxes[j].length &&
             boxes[i].width < boxes[j].width
           ) {
             dp[i] = Math.max(dp[i], boxes[i].height + dp[j]);
           }
         }
 
         maxHeight = Math.max(maxHeight, dp[i]);
       }
 
       return maxHeight;
     }
 
     let length = [4, 1, 4, 10];
     let width = [6, 2, 5, 12];
     let height = [7, 3, 6, 32];
 
     console.log(
       "The maximum possible height of stack is " +
         maxStackHeight(length, width, height)
     );

C#

using System;
using System.Linq;
 
public class BoxStacking {
    public class Box : IComparable<Box> {
        public int length;
        public int width;
        public int height;
 
        public Box(int length, int width, int height) {
            this.length = length;
            this.width = width;
            this.height = height;
        }
 
        public int CompareTo(Box b) {
            return (this.length * this.width).CompareTo(b.length * b.width);
        }
    }
 
    public static int maxStackHeight(int[] length, int[] width, int[] height) {
        int n = length.Length;
        Box[] boxes = new Box[3 * n];
 
        int k = 0;
        for (int i = 0; i < n; i++) {
            boxes[k++] = new Box(length[i], width[i], height[i]);
            boxes[k++] = new Box(width[i], height[i], length[i]);
            boxes[k++] = new Box(height[i], length[i], width[i]);
        }
 
        Array.Sort(boxes);
 
        int[] dp = new int[3 * n];
        int maxHeight = 0;
 
        for (int i = k - 1; i >= 0; i--) {
            dp[i] = boxes[i].height;
            for (int j = i + 1; j < k; j++) {
                if (boxes[i].length < boxes[j].length && boxes[i].width < boxes[j].width) {
                    dp[i] = Math.Max(dp[i], boxes[i].height + dp[j]);
                }
            }
 
            maxHeight = Math.Max(maxHeight, dp[i]);
        }
 
        return maxHeight;
    }
 
    public static void Main(string[] args) {
        int[] length = { 4, 1, 4, 10 };
        int[] width = { 6, 2, 5, 12 };
        int[] height = { 7, 3, 6, 32 };
 
        Console.WriteLine("The maximum possible height of stack is " + maxStackHeight(length, width, height));
    }
}

Output

The maximum possible height of stack is 60

Time Complexity: O(n^2)
Auxiliary Space: O(n)

In the above program, for boxes of dimensions of {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} on giving the input as {4, 1, 4, 10} for length, {6, 2, 5, 12} for width and {7, 3, 6, 32} for height. Following rotations are possible for the boxes in decreasing order of base area.

32 x 12 x 10 <-
32 x 10 x 12
12 x 10 x 32 <-
7 x 6 x 4      <-
6 x 5 x 4      <-
7 x 4 x 6
6 x 4 x 5
6 x 4 x 7
5 x 4 x 6    <-
3 x 2 x 1    <-
3 x 1 x 2
2 x 1 x 3    <-
The maximum possible height of stack is 60

The height 60 is obtained by boxes { {2, 1, 3}, {3, 2, 1}, {5, 4, 6}, {6, 5, 4}, {7, 6, 4}, {12, 10, 32}, {32, 12, 10}}

Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Box Stacking Problem | DP-22

C++

Java

Python3

C#

Javascript

C++

Java

Python3

Javascript

C#

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US