有关于多背包问题的算法吗？

Question

我的场景是有多个背包，并且它们的容量相同。还有一些物品，每件物品的重量与其价值相同。我正在尝试找到一种算法或论文来让所有垃圾箱获得平衡分配。

有什么算法或者论文吗？

谢谢，伙计们。

Answer 1

一种选择是通过将问题建模为整数线性程序并使用 ILP 软件包求解来计算最佳极小极大解。在这种情况下，极小极大解决方案将在将物品分配到箱子后最小化最重箱子的重量，这往往会减少箱子之间重量的变异性。

我们得到：

• W：每个仓的重量容量

• w_i：对于每个 i

  ，第 i 项的重量

变量如下。

• x_ij：如果项目 i 分配给 bin j，则等于 1，否则对于所有 i,j 对

  等于 0

• z：分配后最重箱子的重量。

制定的ILP如下。

最小化 z

须遵守：

每件物品都被分配到一个箱子

对于每个 i

，_Σj_xij

= 1

每个bin的重量不能超过z

Σ_ix_ij - 每个 j

z ≤ 0

如果z的最优值超过W，则表示不存在可行解；否则 xij 的最优值构成将项目分配到箱中，从而产生最优极小极大解。

请注意，最优性迫使 z 下降到最重箱子的重量。