2D箱与堆垛高度限制

没有重复我一直在试图解决这个问题的一个变种2D：Box stacking problem 2D箱与堆垛高度限制

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

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

箱子的底部必须大于或等于（不能大于）它。

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

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

编辑：

我意识到，如果你创建一个像你这样的3-d变种做每一个项目的两个可能的旋转，这个问题就变得非常相似的背包问题。由于必须使用该排序列表的子集以的顺序构建最佳塔，那么我们必须选择要采取哪一个。但是，我仍然不知道如何确保没有重复。任何帮助解决这个问题？感谢

编辑2：

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

来源

2013-02-14 William Rookwood

它不清楚目标是什么。在单个堆栈中的最低限度以下的盒子？正常的问题表明，目标是可能的最高堆栈，但由于我们在这里有一个“限制”，所以目标必须不同。 – 2013-02-14 22:06:13

是的，目标仍然是高度限制以下的最高堆叠。 – 2013-02-14 22:40:16

@TylerDurden，是的。 – 2013-02-15 02:49:53

好吧，我发现解决方案只是0-1样式，除了布尔表之后，意识到顺序并不重要，因为任何一组二维矩形都可以分类到一个遵守限制条件的塔中。

来源

2013-02-16 21:42:43

请你详细解释一下 – 2013-02-25 18:39:25

任何一组二维矩形都不一定被分类到一个遵守高度限制的塔内。即使可以，你仍然需要决定使用哪个方向来放置特定的盒子（旋转它以便底座最大，如果适合的话，可以将更宽的矩形堆叠在顶部，但不会那么高。）

非0/1版本允许多个矩形实例，通过动态编程解决，创建两个矩形，旋转方式不同，对矩形数组进行排序（强制执行部分顺序，以便如果矩形i与一个指定的旋转，可以适应矩形j的顶部，具有指定的旋转，那么我必须小于j），然后计算i = 0 ... n可以通过以塔结束的塔的最大高度ith具有指定旋转的框。

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

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

来源

2015-10-21 01:07:36

2D箱与堆垛高度限制

回答

相关问题