dynamic-programming - 使用堆叠箱 build 的最高塔

Question

我试图解决的问题称为盒子堆叠。这是描述:
盒子堆叠

给定一组 n 种矩形 3-D 框，其中第 i^ 个框的高度为 h(i)、宽度为 w(i) 和深度为 d(i)(均为实数)。您想创建一堆尽可能高的盒子，但是如果下部盒子的二维底面的尺寸都严格大于二维底面的尺寸，则只能将一个盒子堆叠在另一个盒子的顶部。 D 底座较高的盒子。当然，您可以旋转一个盒子，让任何一侧都作为它的基础。也允许使用相同类型框的多个实例。

我想到了以下解决方案:
让一个框表示为 (h,w,d)。
然后我们可以表示所有框的序列，如 (h1, w1, d1), (h2,w2,d2), (h3,w3,d3)。
为了照顾我们可以使用任何旋转的部分，使用上述顺序，我将
为一个块生成所有可能的排列。因此，对于像 (7,1,2) 这样的块，将有 6 个生成的配置。
为了解决这个问题，我计划首先按宽度降序对盒子进行排序。
然后，我会得到一系列的盒子，比如
(h1, w1, d1), (h2,w2,d2) 等等
然后我使用类似于最长降序子序列的概念来解决问题
设 LDS(i) 是最长的递减子序列，以 i 结尾
然后
LDS(i)= { max[LDS(k)] + kwi 的 i 高度和 dk>di}

有没有人看到上面的错误？

请让我知道上述解决方案是否正确

Answer 1

您的解决方案似乎与此类似:http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/

但最后一句话似乎不清楚/不准确。你只比较一个维度。