我有一个程序可以计算将矩形拼在一起所占用的最小面积。
输入:不同高度和宽度的矩形。
输出:一个包含所有这些矩形的矩形。
规则:矩形不能旋转或滚动，也不能重叠。
我知道这是相关的或可能被定义为装箱问题 (NP-hard)。但是，我为那些算法找到的算法通常会限制例如宽度。我没有这样的限制，唯一的目标是使结果区域尽可能小。
关于什么算法适合获得像样的解决方案的任何指示？
最佳答案
http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapspapers/ICAPS04KorfR.pdf
显然这个问题比乍看起来要难。这是一个有趣的算法，因为它首先猜测一个解决方案然后对其进行改进，所以如果你不想等待最优解，你可以只运行它进行一定数量的迭代以获得近似解(时间越长你运行它，近似值越好)。
关于algorithm - 堆叠矩形以占用尽可能少的空间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/251488/