algorithm - 具有相对成本的一维装箱算法

Question

我想知道如何解决“具有相对成本的一维装箱问题”。我们将 N 个卷（具有给定大小）打包到 M 个箱（具有给定容量）中，并具有每个箱的每个卷的成本矩阵 (NxM)。因此，总成本应该最小化。

你能建议任何算法来解决这个问题吗？或者，可能有任何开源库可以做到这一点？

谢谢！

Answer 1

如果正在考虑的问题是广义分配问题，它是困难的，NP但承认一个近似算法。简而言之，近似比取决于背包问题的近似算法的近似比，而背包问题又允许完全多项式时间近似方案。总共。广义分配问题也允许完全多项式时间近似方案。