破解编码面试第 5 版，9.10

Question

在 Cracking the Coding Interview（第 5 版）中，提出了以下问题：

你有一堆宽度为 w(i)、h(i) 和 d(i) 的 n 个盒子。如果堆叠中的每个盒子在宽度、高度和深度上都严格大于其上方的盒子，则盒子不能旋转并且只能一个接一个地堆叠。实现一种构建尽可能高的堆叠的方法，其中堆叠的高度是每个盒子高度的总和。

我想出了以下不涉及任何动态规划的递归解决方案：

 public static List<Box> stackBoxes(List<Box> boxes){
    if(boxes.size() <= 1){
        return boxes;
    }

    List<Box> temp = new ArrayList<Box>();
    temp = stackBoxes(boxes.subList(1, boxes.size()));
    Box currentBox = new Box(0, 0, 0);
    currentBox = boxes.get(0);

    for(int i = 0; i < temp.size(); i++){
        Box nextBox = new Box(0,0,0);
        nextBox = temp.get(i);
        if(nextBox.x >= currentBox.x && nextBox.y >= currentBox.y 
                && nextBox.z >= currentBox.z){

            List<Box> half1 = new ArrayList<Box>(temp.subList(0, i));
            half1.add(currentBox);

            List<Box> half2 = new ArrayList<Box>(temp.subList(i,  
            temp.size()));

            half1.addAll(half2);
            return half1;
        }
    }

    List<Box> newStack = new ArrayList<Box>();
    newStack.addAll(temp);
    newStack.add(currentBox);
    return newStack;

}

盒子class（x-宽度，y-高度，z-深度）：

public class Box {
    public int x;
    public int y;
    public int z;

    public Box(int x, int y, int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

对我来说，似乎总是只有一个最佳的盒子堆叠，因为堆叠中任何给定位置的任何盒子在宽度、高度和深度上都等于或大于它上面的盒子.因此，从本质上讲，最佳堆叠将是一个有序列表，其中每个框 <= 它下面的框。但是根据书中的解决方案和一些在线解决方案，我认为我误解了这个问题，这是不正确的，所以我希望得到一些帮助。你们中的任何人都可以解释为什么这个问题的解决方案需要寻找每个可能的框组合，而不仅仅是生成一个有序的框列表吗？

谢谢！

Answer 1

考虑只有三个盒子的情况（在 WxDxH 中）1x7x2、1x6x2 和 7x1x5。这些盒子没有严格的排序，因为前两个盒子都放不下第三个盒子。然而，正确的解决方案是第三个盒子本身 (5 > 2+2)。如果我理解你的算法，它不会应付这种情况。该问题的解决方案需要支持多个堆栈并将每个盒子添加到它可以包含的所有堆栈中。

Answer 2

您的解决方案似乎不正确。它总是按某种顺序报告包含所有框的列表。如果你有 3 个盒子 [w10, h10, d10], [w5, h5, d5], [w1, h1, d20] 那么只有前两个形成最高的堆叠。

如果您尝试寻找递归解决方案，您会发现这需要指数时间。动态规划是这里最好的解决方案。只需要二次方时间。

这个想法并不难。您只需制作带有顶点框的定向图，并在两个顶点之间添加边，前提是目标顶点中的框可以放在源顶点中框的顶部。每个顶点的权重是其中框的高度。然后最佳堆栈对应于该图中具有最大顶点权重和的路径。这里的关键是访问过的顶点。所有顶点都应该在开头有 "not yet visited" 标记。每个顶点中的第二个必要字段是聚合的最佳堆栈高度，以该顶点的一个框结尾。第三个属性是对前一个最佳顶点的反向引用。算法从没有传入边的顶点开始。您只需将他们的身高用作最佳身高并将其标记为已访问。在接下来的每个步骤中，您只能访问具有所有传入边和已访问源顶点的顶点。当您访问某个顶点时，您会选择最佳传入边（具有最高聚合高度）。您将当前顶点的高度添加到聚合高度并存储在该顶点中。此外，您还存储从该顶点到最佳路径来自的前一个顶点的反向引用。最后，您应该从没有出边的顶点集中选择最佳顶点。从最佳最终顶点沿着反向参考返回，您重建最佳路径，为您提供最佳堆栈。

破解编码面试第 5 版，9.10

Cracking the Coding Interview 5th Ed., 9.10

java

oop

recursion

dynamic-programming