我有要求，将特定数量的矩形(具有定义的宽度但随机高度)插入另一个矩形(具有定义的高度和与要插入的矩形相同的定义宽度)。这里的目标是，那些插入的矩形应该尽可能地填满目标矩形。
例如:
我不需要让尽可能多的矩形进入黑色，目标是尽可能多地填充黑色矩形，最好的情况是完全填充。
现实中有很多“黑色”矩形和成千上万个“红色”，我正在寻找一种有效的算法来计算。我必须在 ECMA-/Javascript 中实现它，所以它并不是所有平台中最快的。
我研究了一些算法，例如 Richard E. Korf 的“最佳矩形包装”或“Bin packing 问题”，但我无法真正将它们转化为这个特定问题。
有人可以向我推荐一种方法/算法吗？
最佳答案
因为您的红色和黑色三角形都有定义的宽度，所以您可以将问题简化为一条数字线，可以这么说。基本上，如果您曾经翻转过一个红色的边，您很可能最终会浪费空间 - 比以“正常安装”方式放置它浪费的空间要多得多。
考虑到这一点，您可以将问题精确地简化为传统的背包问题，其中容量是黑色矩形的高度，红色三角形的“重量”是它们的高度。宽度完全可以从问题中抽象出来。
另一个优势(正如xvatar所指出的)是候选人的值(value)密度都是平等的。也就是说，您没有传统背包问题所具有的“砖环”问题。考虑到在砖 block 和戒指之间进行选择来填充背包，戒指显然是候选者。在这种情况下，它们都是一样的，因此没有明显的候选对象。
似乎大块很容易候选，但这种贪心的方法行不通。考虑还有 5 个单位空间的场景，我们有 4、3 和 2 block 砖。如果我们采用贪心解决方案，我们添加 4，留下 1 个开放空间。如果我们改为使用 3 和 2，我们将不会剩下 1 个开放空间。
还需要注意的是，一旦您确定了哪些矩形进入，它们进入的顺序就无关紧要了。
关于algorithm - 区域优化算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11455918/