Design and Analysis of Algorithms
You are given a series of boxes. Each box i has a rectangular base with width Wi and length Li, as well as a height Hi. You are stacking the boxes, subject to the following: In order to stack a box i on top of a second box j, the width of box i must be strictly less than the width of box j and the length of box i must be strictly less than the length of box j (assume that you cannot rotate the boxes to turn the width into the length). Your job is to make a stack of boxes with total height as large as possible. You can only use one copy of each box. Design a dynamic programming algorithm to solve this problem.
Part a: Draw and explain the DAG corresponding to this problem. Hint: What is a reasonable way to sort the boxes so that all edges go from earlier nodes to later nodes?
Part b: Describe an efficient algorithm to determine the height of the tallest possible stack. You do not need to write pseudocode (though you can if you want to), but in order to get full credit, you must include all the details that someone would need to implement the algorithm. Hint: think about what the subproblems should be.