区域优化算法

Question

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

例如：

在此处输入图片说明

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

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

我研究了一些算法，例如 Richard E. Korf 的“Optimal Rectangle Packing”或“Bin Packagings Problems”，但我无法真正针对这个特定问题翻译这些算法。

有人可以推荐我一种方法/算法吗？

Answer 1

因为你的红色和黑色三角形都有一个定义的宽度，所以可以说，你可以将问题简化为数轴。基本上，如果你把红色的一面翻过来，你很可能最终会浪费空间——比以“正常安装”的方式放置它浪费的空间要多得多。

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

另一个优点（正如 xvatar 所指出的）是候选人的价值密度都是相等的。也就是说，你没有传统背包问题的“砖环”问题。考虑到砖块和戒指之间的选择来填充您的背包，戒指是显而易见的候选者。在这种情况下，它们都是相同的，因此没有明显的候选者。

看起来大块是容易的候选者，但这种贪婪的方法行不通。考虑剩下 5 个空间单位的场景，我们有 4、3 和 2 个砖块。如果我们采用贪心解决方案，我们添加 4，留下 1 个开放空间。如果我们改为使用 3 和 2，我们将没有剩余的 1 个空地。

还需要注意的是，一旦您确定了矩形的位置，它们的顺序就无关紧要了。