区域优化算法(Area optimization algorithm)

区域优化算法(Area optimization algorithm)

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

例如：

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

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

我查看了一些像Richard E. Korf的“最佳矩形包装”或“Bin填充问题”这样的算法，但我无法真正翻译这些具体问题。

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

I'm having the requirement, to insert a specific amount of rectangles (which have a defined width but a random height) into another rectangle (which has a defined height and the same defined width as the rectangles to insert). The goal here is, that those inserted rectangles should fill-out the target rectangle as much as possible.

For instance:

I don't need to get as much rectangles as possible into the black, the goal is to fillout the black rect as much as possible, best case, entirely.

In reality, there are many "black" rectangles and thousands of "reds", I'm looking for an effective algorithm to calculate. I have to implement this in ECMA-/Javascript so it's not really the fastest of all platforms.

I looked into some algos like Richard E. Korf's "Optimal Rectangle Packing" or "Bin packings problems", but I couldn't really translate those for this specific problem.

Can somebody recommend me a method/algorithm ?

最满意答案

因为您的红色和黑色三角形都具有已定义的宽度，所以可以将问题减少到数字线。 基本上，如果你曾经翻过一个红色的东西，你很可能最终会浪费空间 - 浪费太多的空间而不是以“正常拟合”的方式。

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

另一个优点（正如xvatar所指出的）是候选者的价值密度都是相等的。 也就是说，你没有传统背包问题所带来的“砖环”问题。 鉴于砖和戒指之间的选择，以填补你的背包，戒指显然是候选人。 在这种情况下，他们都是一样的，所以没有明显的候选人。

似乎大块是容易的候选人，但这种贪婪的方法不会飞。 考虑剩下5个单位空间的场景，我们有4个，3个和2个砖块。如果我们选择贪婪的解决方案，我们添加4个，留下1个空地。 如果我们改为3和2，我们就不会剩下1个开放空间。

它还需要注意的是，一旦你确定了哪些矩形进入，它们进入的顺序并不重要。

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

Because your red and black triangles both have a defined width, you can reduce the problem to a number line, so to speak. Basically, if you ever flipped a red one on its side, you'd most likely end up with wasted space - much more wasted space than putting it in the 'normal fitting' way.

So with this in mind, you can reduce the problem exactly to the traditional knapsack problem where the capacity is the height of the black rectangle and the 'weight' of the red triangles are their height. The width can be entirely abstracted out of the problem.

Another advantage (as pointed out by xvatar) is that the value density of the candidates are all equal. That is to say that you don't have the "brick-ring" issue the traditional knapsack problem has. Given the choice between bricks and rings to fill your knapsack with, the rings are obvious candidates. In this case, they're all the same so there are no obvious candidates.

It would seem the big blocks are easy candidates, but this greedy approach doesn't fly. Consider the scenario where there are 5 units of space left, and we have bricks of 4, 3 and 2. If we go with the greedy solution, we add the 4, leaving 1 open space. If we would instead have gone with 3 and 2, we would not have the 1 open space remaining.

It also stands to note that once you have identified what rectangles go in, it doesn't matter what order they go in.

Further reading: http://en.wikipedia.org/wiki/Knapsack_problem