我有一些不同大小的长方形盒子和一个更大的长方形盒子我需要在更大的盒子里放入不同种类的盒子的最大数量。在任何情况下,每种类型的箱子都需要满足一定的最小数量。基本上,我需要解决约束优化问题。我该怎么做?

最佳答案

不幸的是,这个问题没有多项式时间算法,也就是说,它是NP难的。
所以试试搜索。把盒子从大到小排序可能会有帮助(按区域或一侧排序,不能说哪个更好,取决于搜索方式)。
如果速度远不能接受,尝试partial greedy以获得一个相当好的解决方案。

07-25 20:38