algorithm - 物体定位算法

Question

我想知道这个问题是否有“最佳”解决方案:

我有一个 n x m(像素)大小的空间，上面有 p 个预先存在的矩形 - 各种大小的对象。现在我想在这个空间中放置 q 个(相同大小的)新对象，没有任何重叠。

我想出的算法:

1. 创建数组 A[][]，大小为 [(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

2. 迭代 p 中的所有元素，并为每个元素:

   将 A[][] 中的所有字段标记为已占用，元素“位于”的位置

3. 将q中的所有元素放在A[][]中字段未标记的相应位置

(天哪，我希望我能让大家理解...)

有没有更好的方法来做到这一点？非常感谢任何帮助!

Answer 1

从互联网上的简短搜索来看，最佳矩形包装似乎是 NP-hard问题。我猜想学术界的聪明人为此找到了一些近似算法，所以它是谷歌搜索的一个选项。

但我会先尝试让简单的方法起作用:

1. 根据对象的宽度将对象分成大小
2. 尝试将它们从大到小逐行放置。

我的猜测是，在许多情况下，这种天真的解决方案会奏效。