You have n boxes with square bases, the i -th box has height h i , each side of
ID: 3845179 • Letter: Y
Question
You have n boxes with square bases, the i-th box has height hi, each side of the base has length si, and the weight of the box is wi. You can stack box j on top of box k if sj sk and wj wk. So you can only stack a box on top of another if it’s both no heavier and has a base no bigger.
Let H(i) be the tallest stack of boxes you can build. The tallest stack of boxes that you can build with box j on the top is
The overall maximum height stack will be
A. Using pesudocode, implement a dynamic programming solution to this problem.
B. Analyze the running time of the dynamic programming algorithm.
H(j) = max(H (i)) + h KJ wi2WJ sizsjExplanation / Answer
HI, Please find my code in Java, this is not running code, this is psudocode.
Lets assume, this is the Box class:
public class Box {
private int weight, base, height;
public Box(int w, int l, int h) {
weight = w;
base = l;
height = h;
}
public boolean canPlaceAbove(Box b) {
return b == null ||
(this.weight < b.weight &&
this.base < b.base);
}
}
// Problem Solution
public class BiggestStack {
public static ArrayList<Box> buildTallestStack(Box[] boxes) {
if (boxes == null) return null;
return buildTallestStack(boxes, null);
}
private static ArrayList<Box> buildTallestStack(Box[] boxes, Box bottom) {
int maxHeight = 0;
ArrayList<Box> maxStack = null;
for (Box box : boxes) {
if (box.canPlaceAbove(bottom)) {
ArrayList<Box> boxStack = buildTallestStack(boxes, box);
int height = getStackHeight(boxStack);
if (height > maxHeight) {
maxHeight = height;
maxStack = boxStack;
}
}
}
if (maxStack == null) maxStack = new ArrayList<Box>();
if (bottom != null) maxStack.add(0, bottom);
return maxStack;
}
private static int getStackHeight(List<Box> boxes) {
int height = 0;
for (Box b : boxes) height += b.height;
return height;
}
}
Time Complexity: O(n^2)
Auxiliary Space: O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.