面积优化算法

Question

我需要将特定数量的矩形(具有定义的宽度，但高度是随机的)插入到另一个矩形(该矩形具有定义的高度和与要插入的矩形相同的定义宽度)。这里的目标是，这些插入的矩形应该尽可能多地填充目标矩形。

例如：

​

​

我不需要将尽可能多的矩形填充到黑色中，目标是尽可能多地填充黑色矩形，最好的情况是完全填充。

在现实中，有许多“黑色”矩形和数千个“红色”，我正在寻找一个有效的算法来计算。我必须在ECMA-/Javascript中实现它，所以它并不是所有平台中最快的。

我研究了一些算法，比如Richard E.Korf的“最佳矩形打包”或“装箱问题”，但我不能真正将它们翻译为这个特定的问题。

有人能给我推荐一个方法/算法吗？

Answer 1

因为您的红色和黑色三角形都有定义的宽度，所以您可以将问题简化为数字行。基本上，如果你把红色的翻转过来，你很可能会浪费空间--比起把它放在正常的位置上，浪费的空间要多得多。

因此，考虑到这一点，您可以将问题精确地简化为传统的背包问题，其中容量是黑色矩形的高度，红色三角形的“权重”是它们的高度。宽度可以完全从问题中抽象出来。

另一个优势(正如xvatar所指出的)是所有候选者的价值密度都是相等的。这就是说，你没有传统背包问题中的“砖环”问题。如果要在砖块和戒指之间进行选择来装满你的背包，那么戒指是显而易见的候选者。在这种情况下，它们都是一样的，所以没有明显的候选者。

大块似乎是简单的候选者，但这种贪婪的方法行不通。假设还有5个单位的空间，我们有4块、3块和2块。如果我们使用贪婪的解决方案，我们添加4，留下1个开放空间。如果我们转而使用3和2，我们就不会有剩余的1个开放空间。

同样值得注意的是，一旦你确定了矩形的位置，它们的顺序就不重要了。

进一步阅读：http://en.wikipedia.org/wiki/Knapsack_problem