Question 1:
In stores, boxes should be placed in an organized way otherwise it will be messy. Given a collection of boxes, it is requested to place them on top of each other to reach the
minimum possible height. There is a condition, where a box cannot be placed on top of another box unless the area of its 2D base is smaller or equal of the 2D base of the lower box. It is allowed to rotate any box to use any two sides as its base.
For example, consider below 4 boxes where each box has the following dimensions
Input:
Box 1: (2,1,3), Box 2:(6,3,8) Box 3: (4,2,5), Box 4:(3,1,6),
Output:
From bottom to top as follows:
In the bottom Box 2 on the base (6,8) and height 3,
On top of it Box 3 on the base (4,5) and height 2,
Then Box 4 on the base (6,3) and height 1,
Finally Box 1 on the base (2,3) and height 1.
The total height is 7
a) Describe how a brute-force approach algorithm would solve the above problem , and explain its complexity .
b) Design an algorithm to solve the above scenario for N boxes.
c) Develop a python code to implement your efficient algorithm.
d) Prepare a brief report comparing the two algorithms