[CareerCup] 9.10 Stack Boxes 垒箱子问题 - Grandyang - 博客园

[CareerCup] 9.10 Stack Boxes 垒箱子问题 - Grandyang - 博客园

[CareerCup] 9.10 Stack Boxes 垒箱子问题

 

9.10 You have a stack of n boxes, with widths w., heights hir and depths drThe 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 build the tallest stack possible, where the height of a stack is the sum of the heights of each box.

 

开始看到这题时，以为是3.4 Towers of Hanoi 汉诺塔，其实不太一样，这道题只是单纯的让我们垒箱子而已，大的在最底下，问我们能垒出的最大高度是多少。也是一道用递归来解的题，首先我们要先实现箱子类Box，里面包含了箱子的尺寸宽，高和深度，然后还要有一个成员函数canBeAbove，用来判断当前箱子能否放到另一个箱子的上面，还有一个静态函数，是求一摞箱子的总高度的。然后我们对每个箱子都调用一次递归，然后维护一个最大值，每次递归都更新这个最大值，那么最终递归结束后这个最大值就是所求，参见代码如下：

Read full article from [CareerCup] 9.10 Stack Boxes 垒箱子问题 - Grandyang - 博客园