In stores, boxes should be placed in an organized way otherwise it will be messy. Given...

Transcribed Image Text:

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 [Explanation: as we can see that the first box in the bottom is the box 2 with base 6x8 and height 3, then box3 with base 4x5 and height 2, 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 shortest possible stack] a) Describe how a brute-force approach algorithm would solve the above problem (4 marks), and explain its complexity (2 marks). b) Design an algorithm to solve the above scenario for N boxes. (6 marks) [The efficiency of your algorithm is the main driver of the mark], and analyze the complexity of your solution. (2 marks) [full explanation of your answer should be provided] c) Develop a python code to implement your efficient algorithm. (10 marks) [The marks depend on the correctness of the code, indentation, comments, test-case] d) Prepare a brief report (250 words) comparing the two algorithms (6 marks) 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 [Explanation: as we can see that the first box in the bottom is the box 2 with base 6x8 and height 3, then box3 with base 4x5 and height 2, 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 shortest possible stack] a) Describe how a brute-force approach algorithm would solve the above problem (4 marks), and explain its complexity (2 marks). b) Design an algorithm to solve the above scenario for N boxes. (6 marks) [The efficiency of your algorithm is the main driver of the mark], and analyze the complexity of your solution. (2 marks) [full explanation of your answer should be provided] c) Develop a python code to implement your efficient algorithm. (10 marks) [The marks depend on the correctness of the code, indentation, comments, test-case] d) Prepare a brief report (250 words) comparing the two algorithms (6 marks)

Answer rating: 100% (QA)

a A bruteforce approach algorithm would solve the above problem by generating all possible arrangements of the boxes and checking if each arrangement ... View the full answer