QUESTION

Given a group of boxes, you are requested to arrange these boxes on top of each other to reach the maximum possible height. Note: 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 rotated 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: (4,5,2), Box 2:(3,1,6), Box 3:(3,2,1),

Box 4:(6,8,3)

Output:

From bottom to top as follows:

Box 4 on the base (6,3) and height 8,

then Box 1 on the base (4,2) and height 5, then Box 2 on the base (1,3) and height 6, finally, on top Box 3 on the base (2,1) and height 3.

The total height is 22

[Explanation: as we can see that the first box in the bottom is the box # 4 with base 6x3 and height 8, then box # 1 with base 4x2 and height 5, and so on. This arrangement of boxes fulfils the constraint mentioned above: “the dimensions of the 2D base of the lower box are each strictly larger than those of the 2D base of the higher box”. This solution also satisfies the tallest possible stack]

  1. Describe how a brute-force approach algorithm would solve the above problem , and explain its complexity .
  2. Design an algorithm to solve the above scenario for N boxes.[full explanation of your answer should be provided]
  3. What will happen to the complexity of your efficient algorithm if the constraint “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” is not required anymore?
  4. Develop a python code to implement your efficient algorithm.

Public Answer

KZ51V9 The First Answerer