java - 破解编码面试第五版，9.10

Question

在《破解编码面试》(第五版)中，提出了以下问题:

你有一堆 n 个盒子，宽度分别为 w(i)、h(i) 和 d(i)。这些盒子不能旋转，并且只能在堆叠中的每个盒子的宽度、高度和深度都严格大于其上面的盒子的情况下才能堆叠在一起。实现一种方法来构建尽可能高的堆栈，其中堆栈的高度是每个盒子的高度之和。

我想出了以下不涉及任何动态编程的递归解决方案:

 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;

}

盒子类(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

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