You are given a series of boxes. Each box i has a rectangular base with width Wi

Question

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 Directed Acyclic Graph 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.

Treat single arithmetic operations (addition, subtraction, multiplication, and division) as constant time operations.

Explanation / Answer

import java.util.Arrays; import java.util.Collections; import java.util.Comparator; public class BoxStacking { public int solve(int [][] x){ Box [] boxes = new Box[x.length*3]; for (int i = 0; iboxes[i-1].depth){ if(optHeight[maxHeightIndex]

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.