Stack of Boxes

作者 QIFAN 日期 2016-10-21
Stack of Boxes

Source: Cracking the Code Interview 8.13


Description

You have a stack of n boxes, with widths $w_i$, heights $h_i$, and depths $d_i$ . The boxes
cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly
larger than the box above it in width, height, and depth. Implement a method to compute the
height of the tallest possible stack. The height of a stack is the sum of the heights of each box.

有n个箱子,长宽高分别是$w_i$,$d_i$,$h_i$。规定一个箱子可以放在另一个箱子上的情况有且只有该箱子的长宽高均小于另一箱子。求这堆箱子可以叠起的最高高度(高度应为所有叠起箱子的高度之和)。

思路

对于这种乱序的叠加问题,首先想到就是把数组排个序,箱子有三个维度,就选择高度来排序,因为从最下面的箱子(最大)开始叠,所以降序。

对于同一堆箱子,高度的不同取决于最底下的箱子,若底箱子一样,则最高高度必然是一样的。
对于每一个箱子,有两个选择,叠上去或者不叠上去。
假设原有箱子堆最高的箱子为i,现有箱子j

  • 若叠上去,则最高高度是在原高度加上j的高度加上以箱子j为底的那部分高度
  • 若不叠上去,则最高高度是原高度加上以箱子i为底的那部分高度

就像一颗决策树,每一次选择不同,箱子的叠放也不同,所以每次都需要算出两种不同决策的高度进行比较。

假设Box的API如下:

class Box
int height
int width
int depth
boolean isSmaller(Box b) // b是否比自己小

Solution

int stackHeight(ArrayList<Box> boxes) {
// 按高度降序
Collections.sort(boxes, new BoxComparator());
// heights[i] 代表了放入箱子i的最高高度,若不放入则height[i] = 0;
int heights[] = new int[boxes.size()];
return stackHeight(boxes, null, 0, heights);
}
int stackHeight(ArrayList<Box> boxes, Box bottom, int i, int[] heights) {
// base case, 没有箱子可加
if(i >= boxes.size()) return 0;
// 如果箱子i加入箱子堆成为新的底
Box new = boxes.get(i);
int heightWithBoxi = 0;
// 如果底是null,或者新箱子比现在顶部(之后的底)的箱子小,则加入
if(bottom == null || new.isSmaller(bottom)) {
// 如果之前的方法没有放入heights[i],则计算新的高度。
if(heights[i]==0) {
heights[i] = new.height + stackHeight(boxes, new, i + 1, heights);
}
heightWithBoxi = heights[i];
}
// 如果箱子i不加入
int heightWithoutBoxi = stackHeight(boxes, bottom, i + 1, heights);
return Math.max(heightWithBoxi, heightWithoutBoxi);
}
class BoxComparator implements Comparator<Box> {
@Override
public int compare (Box x, Box y) {
return y.height - x.height;
}
}

分析

这道题真的是很乱。最重要的是弄清楚height[i]的意思,不像之前的DP一样代表放了i个箱子后的高度,而是以箱子i为底的最高高度。因为每一次新加的箱子都可能会使整个排列打乱,所以唯一可以依靠的就是最下面的底,如果底一样的同一堆箱子,且最高高度一致,那向上叠的箱子必然是一样的。

时间复杂度的话,如果有N个箱子,理论上决策树会有 $2^N$个叶子,一共有N层,因此最多为 $O(N * 2^N)$.