algorithm - 将矩形盒子放入更大的矩形盒子中

Question

我有一些不同尺寸的矩形盒子和一个更大的矩形盒子。我需要在更大的盒子中放入尽可能多的不同类别的盒子。在任何情况下，每个类别都需要容纳一定的最小数量的盒子。基本上，我需要解决约束优化问题。我该如何处理？

Answer 1

不幸的是，这个问题没有多项式时间算法，即它是 NP 难的。

所以尝试搜索。将框从大到小排序可能会有所帮助。（按区域或一侧，不能说哪个更好，取决于您的搜索方式）。

如果速度远远不能接受，尝试部分贪婪以获得相当好的解决方案。