一维binp​​acking算法相对成本 [英] One-dimensional binpacking algorithm with relative costs

问题描述

我不知道如何解决一维binp​​acking问题相对成本。我们收拾ñ卷（与给定的尺寸）为M档（给定容量），并且每个每个仓每卷成本矩阵（N×M个）。所以，总成本应最小。

I'm wondering how to solve "One-dimensional binpacking problem with relative costs". We pack N volumes (with given sizes) into M bins (with given capacities) and have the matrix (NxM) of costs of each volume per each bin. So, the total cost should be minimized.

您可以提供意见的算法求解呢？或者，也许，任何开源的lib这样做？

Can you advice any algorithm for solving this? Or, probably, any open-source lib for doing this?

谢谢！

推荐答案

如果所考虑的问题是推广分配问题，这是 NP -hard但承认了的近似算法。从一个简单的介绍一下，近似比依赖于近似算​​法为背包问题近似比，这反过来又承认一个完全多项式时间近似方案。总共。广义分配问题也承认一个完全多项式时间近似方案。

If the problem under consideration is the 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, which in turn admits a fully polynomial time approximation scheme. In total. the generalized assignment problem also admits a fully polynomial time approximation scheme.

这篇关于一维binp​​acking算法相对成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！