区域优化算法

Question

4

我有一个需求，需要将一定数量的矩形（宽度已定义但高度随机）插入到另一个矩形中（高度已定义且与要插入的矩形相同）。这里的目标是让这些插入的矩形尽可能填满目标矩形。

例如：

我不需要在黑色区域内放置尽可能多的矩形，目标是尽可能填满黑色矩形，最好是完全填满。

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

我研究了一些算法，如Richard E. Korf的“Optimal Rectangle Packing”或“Bin packing problems”，但我无法将其转化为这个特定问题。

有人能推荐一种方法/算法吗？

- jAndy

4

这听起来像是背包问题。 - nhahtdh

2

由于所有宽度都相同，您可以将问题简化为一维。 - xvatar

矩形的尺寸是整数吗？它们有多大（高度可以达到十亿级别吗）？ - nhahtdh

@corsiKa：1）&& 3），这是出于商业目的，旨在将自动扩散的广告尽可能少地占用列空间。因此，为获取第一列的完美结果而采取“贪婪”方法不一定是最好的选择，这会留下更多“开放空间”的其他列。顺便感谢你的答复。 - jAndy

@corsiKa：目前还不是纯粹的商业项目，更多的是技术演示，我们想要看到JavaScript在这个计算点上的表现有多快。因此，规则仍然是尽可能有效地利用可用空间。 - jAndy

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- corsiKa · Accepted Answer

由于您的红色和黑色三角形都有一个定义好的宽度，您可以将问题简化为一个数轴。基本上，如果您将红色三角形翻转，最终会浪费更多空间，比将其以“正常适配”的方式放置要浪费更多的空间。

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

另一个优点（正如xvatar所指出的）是候选项的价值密度都是相等的。也就是说，您没有传统背包问题中的“砖环”问题。如果要用砖块和环来填充您的背包，那么显然选择环是更好的。在这种情况下，它们都是一样的，因此没有明显的候选者。

看起来大块很容易成为候选者，但这种贪心的方法行不通。考虑到还剩下5个空位的情况下，我们有4、3和2个单位的砖块。如果我们采用贪婪的解决方案，我们会添加4，留下1个开放空间。如果我们改用3和2，我们就不会剩下1个开放空间。

还需要注意的是，一旦确定了要添加的矩形，它们的顺序就不重要了。