我对此处建议的盒子堆叠算法有疑问: http://people.csail.mit.edu/bdean/6.046/dp/
算法做出了一些错误的假设: 在视频中，它说我们“按照底面积递减的顺序对箱子进行排序……等等”。 我们这样做是因为只有当上方放置的盒子的宽度和深度分别小于下方盒子的宽度和深度时，才能将盒子放在另一个盒子的顶部。 但是如果盒子 B_1 的底面积比盒子 B_2 大，这并不意味着它的宽度和深度也大于盒子 B_2 的宽度和深度。
例如，一个 1x8 基本尺寸的盒子比一个 2x3 尺寸的盒子有更大的基本面积，但仍然:1<2(和 1<3)，因此我们不能将盒子 B_2 堆叠到 B_1 上。 我在这里错过了什么？
最佳答案
这是必要条件与充分条件的问题。的确，你可能会遇到 B_2 无法堆叠在 B_1 上的情况，但在这种情况下，B_1 也无法堆叠在 B_2 上，因此在考虑顺序中切换它们没有任何值(value)。也就是说，如果 B_a 的基数大于 B_b，我们就知道 B_a 不能堆叠在 B_b 上(因为它至少有一个维度违反了约束)。
换句话说:在最优堆叠的箱子中，所有箱子都按底面积递减的顺序排列。因此，如果所有框的列表按基面积递减排序，则最佳堆栈保证是所有框列表的子序列——当然，仅由前 k 个框组成的序列也是如此。这意味着，按照动态规划的要求，在检查盒子 k 时，盒子 k 可以停留的最佳堆栈已经在上一轮生成。
关于algorithm - 盒子堆叠算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20005258/