将物品包装成固定数量的箱子

Question

我正在寻找能够以最有效的方式解决我的问题的算法。

问题描述：

我有项目的列表（仅正整数被允许）和相同容量仓的固定数目。到目前为止，我想到了分支定界算法，但我不太确定这是否是最好的方法。

例子：

考虑的项目清单：

(3, 4, 4, 2, 3, 9, 2) 

和能力9各 三个箱，我需要他们收拾这样的：（项目的顺序是无关紧要的）

[3, 4, 2], [4, 3, 2], [9] 

我认为这是一个bin-packing问题的变种（我知道它是NP-complete），但是因为我没有尝试尽量减少使用的垃圾箱数量我想知道是否有更好的解决方案。

Answer 1

这是多纸盒包装问题：

给定一组项目，每一个特定的大小，和一组箱，特定大小的每个 以及 - 有项目的分布至垃圾箱 ，这样没有物品没有被打开并且没有垃圾箱容量被超出？

一般来说这是NP难。但是，有几种特殊情况可能会得到有效解决，大概甚至是最优化。

看到Wolfgang Stille aus Göppingen's thesis

Answer 2

这相当于装箱问题，给出了许多箱，最大限度地挤进箱项目数。

如果最佳解决方案大于或等于列表中的项目数，那么解决方案也是您问题的解决方案。如果最佳解决方案少于列表中的项目数量，则无法解决问题。

由于bin装箱问题是NP-Hard，因此您的问题也没有多项式时间解决方案。您可以使用针对料箱包装问题开发的启发式方法，如最佳拟合，首次拟合等。但他们不保证找到最佳解决方案。