具有相对成本的一维装箱算法
One-dimensional binpacking algorithm with relative costs
我想知道如何解决"One-dimensional binpacking problem with relative costs"。我们将 N 卷（具有给定的大小）打包到 M 个箱子（具有给定的容量）中，并具有每个箱子的每个卷的成本矩阵 (NxM)。因此，总成本应该最小化。
你能建议任何算法来解决这个问题吗？或者，可能有任何开源库可以做到这一点？
谢谢！
如果考虑的问题是generalized assignment problem, it is NP-hard but admits an approximation algorithm. From a brief look, the approximation ratio depends on the approximation ratio of an approximation algorithm for the knapsack problem，这又承认完全多项式时间近似方案。总共。广义分配问题也承认完全多项式时间近似方案。
我想知道如何解决"One-dimensional binpacking problem with relative costs"。我们将 N 卷（具有给定的大小）打包到 M 个箱子（具有给定的容量）中，并具有每个箱子的每个卷的成本矩阵 (NxM)。因此，总成本应该最小化。
你能建议任何算法来解决这个问题吗？或者，可能有任何开源库可以做到这一点？
谢谢！
如果考虑的问题是generalized assignment problem, it is NP-hard but admits an approximation algorithm. From a brief look, the approximation ratio depends on the approximation ratio of an approximation algorithm for the knapsack problem，这又承认完全多项式时间近似方案。总共。广义分配问题也承认完全多项式时间近似方案。