我想知道这个问题是否有“最佳”解决方案:
我有一个 n x m(像素)大小的空间，上面有 p 个预先存在的矩形 - 各种大小的对象。现在我想在这个空间中放置 q 个(相同大小的)新对象，没有任何重叠。
我想出的算法:
- 创建数组 A[][]，大小为
[(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)] 迭代 p 中的所有元素，并为每个元素:
将 A[][] 中的所有字段标记为已占用，元素“位于”的位置将q中的所有元素放在A[][]中字段未标记的相应位置
(天哪，我希望我能让大家理解...)
有没有更好的方法来做到这一点？非常感谢任何帮助!
最佳答案
从互联网上的简短搜索来看，最佳矩形包装似乎是 NP-hard问题。 我猜想学术界的聪明人为此找到了一些近似算法，所以它是谷歌搜索的一个选项。
但我会先尝试让简单的方法起作用:
- 根据对象的宽度将对象分成大小
- 尝试将它们从大到小逐行放置。
我的猜测是，在许多情况下，这种天真的解决方案会奏效。
关于algorithm - 物体定位算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1799662/