重新审视包装问题

Question

我正在开发一个游戏，发现我必须解决的问题来处理与包装问题相似的组件的布局。

总结我需要做的事情，认为我有一个与以下一个类似的空间：

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

其中每个拐角处为4x4，而中央一个为3x3（因此其余的是3x4和4x3）。然后，我有一组元素可以放置在这些块中，这些元素可以从1x1到3x3不等（我认为不需要任何4x4，但不应该更改任何内容）。当然，这些元素不能越界，并且必须完全放在一个单个块中。

哪个可能是分配它们的最佳方法？假设如果不需要，我宁愿不要将它们全部粘在一起（例如，如果周围有足够的空间将它们分开，请不要将两个元素放在一起）。我正在寻找一种简单的算法，也是因为情况非常有限。

奖励问题：除了这9（也许还有其他3-4）之外，还假设其他块与新块相比，我该如何优先考虑这些块？ （我的意思是，直到达到填充阈值之前，我只是不使用额外的块）。

当然，我正在寻找一个总体想法，没有实施:)

Answer 1

这个2d 垃圾箱 问题看起来像是 NP硬.

这是您的几个选择：

• 蛮力或更好的分支和约束。不扩展（根本不扩展！），但会找到最佳解决方案（也许不是我们的一生）。

• 确定性算法：对尺寸最大或最大的侧面进行分类，然后一一浏览该列表，并分配其剩余的最佳位置。这将非常快地完成，但是解决方案可能远非最佳（或可行）。 这是一个很好的图片，显示一个可能出问题的例子。 但是，如果您想保持简单，那就是必须走的路。

• 从确定性算法的结果开始。这将使您在合理的时间内取得非常好的结果，比人类提出的要好。取决于您给它多少时间以及可能是最佳解决方案的问题的困难。那里有几个图书馆，例如 流口水计划者 （开源Java）。