Home » Interview coding problems/challenges

Box Stacking Problem

Here, we are going to learn about the solution of box stacking problem and its C++ implementation.
Submitted by Divyansh Jaipuriyar, on August 22, 2020

Problem statement

You are given a set of n types of rectangular 3-D boxes, where the i^th box has length l(i), width w(i), and height h(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. 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.

Problem description

In simple statement given problem wants you to arrange the boxes one after the another such that the base of the lower level be greater in size on all four direction than the upper box, you are allowed to rotate the box in all direction you can make, after arranging all the boxes in proper manner you need to print the maximum height that you obtained with them.

Input

The first line of the input is the number of test cases T, each test case consists of number of boxes that is N, following N lines consist of the dimension of each box.

Output

You need to print the maximum height that you can obtain by stacking the boxes in proper order.

Examples

Input:
T=2
N=3
4 5 6
8 9 2
6 7 5
N=4
4 2 5
3 1 6
3 2 1
6 3 8

Output:
14
22

Solution Approach

This problem is an application of the Longest increasing subsequence, so will use a dynamic programming approach to solve this problem with the help of structure and STL.

We will generate all the possible rotation of the box, we will make constraint that the width of a box is never more than the length of the box. After finding all the possible combinations of the boxes we will sort it according to the area of the base of the boxes, after that we will apply the longest increasing subsequence logic to find the maximum height.

The logic that we will use:
Let,

LIS(i)=height(i)+max(L(j)),
where j<i and block i can be put on the top of the block j.

LIS is the longest increasing subsequence.

Time Complexity in the worst case for the above approach is: O(n*n)

Space Complexity for the above approach is: O(n)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//we will use vector of
//box to sort it according
//to our need.
struct box {
    //len is the length.
    //wid is the width.
    //hei is the height.
    ll len, wid, hei;
};

//boolean function that will return
//true if area of 'a' box is greater
//than the area of box 'b'.
bool sortbyarea(const box& a, const box& b)
{
    //condition for true.
    if (a.len * a.wid > b.len * b.wid)
        return true;
    else
        return false;
}

//solve function that will return
//maximum height that we can reach.
ll solve(ll l[], ll w[], ll h[], ll n)
{
    //vector of box.
    vector<box> v1;
    //iterate through all boxes.
    for (ll i = 0; i < n; i++) {
        //given dimension(l*w*h)
        v1.push_back({ l[i], w[i], h[i] });

        //another dimension as(l*h*w)
        //here length is maximum among
        //width so we use maxmimum and minimum
        v1.push_back({ max(l[i], h[i]), min(l[i], h[i]), w[i] });

        //another dimension  as(h*w*l)
        //here length is maximum among
        //width so we use maxmimum and minimum
        v1.push_back({ max(w[i], h[i]), min(w[i], h[i]), l[i] });
    }
    //sort according to descending
    //order of their base area.
    sort(v1.begin(), v1.end(), sortbyarea);

    //size of v1 vector after rotation
    //is also included.
    ll n1 = v1.size();
    vector<ll> lis(n1, 0);
    //memset(lis,0,sizeof(lis));

    //traverse all boxes.
    for (ll i = 0; i < n1; i++) {
        //compare all boxes which are
        //below current box.
        for (ll j = 0; j < i; j++) {
            //compare the length of base
            //and the width of the base.
            if (v1[i].len < v1[j].len and v1[i].wid < v1[j].wid) {
                lis[i] = max(lis[i], lis[j]);
            }
        }
        //add current height.
        lis[i] = lis[i] + v1[i].hei;
    }
    //return the maximum value
    //of height that can be formed
    //after stacking the boxes.
    return *max_element(lis.begin(), lis.end());
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        cout << "Enter number of boxes: ";
        ll n;
        cin >> n;
    
        ll l[n], w[n], h[n];
    
        cout << "Enter dimension of boxes:\n";
        for (ll i = 0; i < n; i++)
            cin >> l[i] >> w[i] >> h[i];
    
        cout << "Maximum height that can be reached: ";
        cout << solve(l, w, h, n) << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 2
Enter number of boxes: 3
Enter dimension of boxes:
4 5 6
8 9 2
7 6 5
Maximum height that can be reached: 14
Enter number of boxes: 4
Enter dimension of boxes:
4 2 5
3 1 6
3 2 1
6 3 8
Maximum height that can be reached: 22