2

我一直在尝试解决这个问题的 2D 变体：Box stacking problem

问题是，与原来的不同，同一个盒子的多个实例是不允许的。当然，您仍然可以旋转 2D 矩形。

还有一个高度限制，所以塔必须小于或等于这个限制。

一个盒子在另一个盒子下面的底部必须大于或等于（严格来说不是更大）它。

我一直在尝试应用 LIS 算法，并且似乎处理了其他限制，但我想不出如何解释无重复规则。

所以我的主要问题是，如果你试图最大化堆栈的高度并将其保持在限制以下，你如何解释无重复规则？谢谢

编辑：

我意识到，如果您像为 3-D 变体一样为每个项目创建两个可能的旋转，那么这个问题将变得非常类似于 0-1 背包问题。由于必须使用此排序列表的子集来构建最佳塔，因此我们必须选择要使用的塔。但是，我仍然不知道如何确保没有重复。解决这个问题有什么帮助吗？谢谢

编辑2：

我找到了这个链接：http ://courses.csail.mit.edu/6.006/fall10/handouts/recitation11-19.pdf 第4页描述了如何解决单实例3D最大高度版本，但是我认为这会不适用于高度限制版本，因为它返回每次调用的最大高度。也许这可以修改以适应高度限制？

4

2 回答 2

0

好的，所以我发现解决方案只是 0-1 样式，但在意识到顺序并不重要后使用布尔表，因为任何一组 2D 矩形都可以分类到遵守限制的塔中。

于 2013-02-16T21:42:43.293 回答
0

任何一组 2D 矩形都不一定会被分类成遵守高度限制的塔。即使可以，您仍然需要决定对特定盒子使用哪个方向（旋转它以使底座最大，如果合适，可以使更宽的矩形堆叠在顶部，但不会那么高。）

允许矩形的多个实例的非 0/1 版本通过动态编程解决，方法是创建两个矩形，以不同方式旋转，对矩形数组进行排序（强制偏序，因此如果矩形 i，具有指定的旋转, 可以适合矩形 j 的顶部，具有指定的旋转，然后 i 必须小于 j)，然后计算 i=0...n 可以通过以第 i 个框结束的塔达到的最大高度指定的旋转。

部分顺序是必需的。在 0/1 情况下，不允许多个矩形/框，似乎您必须生成所有矩形/框的所有可能旋转的集合，对每个矩形/框进行排序并计算其最大高度，这不违反任何条件，例如通过动态编程，然后跟踪所有子集上可能的最高堆栈高度（请注意，有可能的子集的指数数量，如在旅行商问题的动态规划解决方案中，远小于一组可能排序的阶乘数。）特别是解决方案http://courses.csail.mit.edu/6.006/fall10/handouts/recitation11-19.pdf看起来不正确：如果 i < j 但是方向为 x 的框 i 可以放在方向为 y 的框 j 的顶部，那么在方向为 x 的框 i 中结束的最高塔可能包含方向为 y 的框 j，当H(i,R) 的计算与公式相矛盾。

请注意，在 0/1 情况下，创建重复项的策略似乎也失败了，因为是否可以将第 j 个框放在第 i 个框的顶部不仅取决于 i，还取决于 i 下面是否有第 j 个框的旋转版本在堆栈中。因此，您似乎需要存储不包含任何可能的盒子子集的最高堆栈，在这种情况下，我们将返回为每个盒子子集计算最高堆栈。

于 2015-10-21T01:07:36.467 回答