我有一个要求，将特定数量的矩形（具有定义的宽度但随机高度）插入另一个矩形（具有定义的高度和与要插入的矩形相同的定义宽度）。这里的目标是，那些插入的矩形应该尽可能地填充目标矩形。
例如：
我不需要尽可能多的矩形进入黑色，目标是尽可能多地填充黑色矩形，最好的情况是完全。
实际上，有许多“黑色”矩形和数千个“红色”，我正在寻找一种有效的算法来计算。我必须在 ECMA-/Javascript 中实现它，所以它并不是所有平台中最快的。
我研究了一些算法，例如 Richard E. Korf 的“Optimal Rectangle Packing”或“Bin packings questions”，但我无法真正针对这个特定问题翻译这些算法。
有人可以推荐我一种方法/算法吗？
因为你的红色和黑色三角形都有一个定义的宽度，你可以将问题简化为数轴，可以这么说。基本上，如果您将红色的一侧翻转过来，您很可能最终会浪费空间 - 比以“正常装配”方式放置更多的空间。
因此，考虑到这一点，您可以将问题精确地简化为传统的背包问题，其中容量是黑色矩形的高度，红色三角形的“重量”是它们的高度。宽度可以完全从问题中抽象出来。
另一个优点（正如 xvatar 所指出的）是候选人的价值密度都是相等的。也就是说，您没有传统背包问题的“砖环”问题。考虑到在背包和戒指之间进行选择来填充您的背包，戒指是显而易见的候选者。在这种情况下，它们都是相同的，因此没有明显的候选者。
看起来大块是容易的候选者，但这种贪婪的方法行不通。考虑剩下 5 个单位空间的场景，我们有 4、3 和 2 个砖块。如果我们采用贪婪解决方案，我们添加 4 个，留下 1 个开放空间。如果我们改为使用 3 和 2，我们将没有剩余的 1 个开放空间。
还需要注意的是，一旦您确定了哪些矩形进入，它们进入的顺序无关紧要。