Box Stacking Problem
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.
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.
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.
You need to print the maximum height that you can obtain by stacking the boxes in proper order.
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
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:
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)
Output:need an explanation for this answer? contact us directly to get an explanation for this answer