algorithm - 将元素包装到固定数量的箱子中

Question

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

问题描述:

我有一个项目列表(只允许使用正整数)和固定数量的相同容量的箱子。到目前为止，我考虑过分支定界算法，但我不太确定在这种情况下它是否是最佳方法。

示例:

给定一个项目列表:

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

和三个容量为9的箱子我需要这样包装它们:(元素的顺序无关紧要)

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

我认为这是装箱问题的一个变体(我知道它是 NP-complete)，但由于我不是要尽量减少使用的箱子数量，我想知道是否有更好的解决方案。

Answer 1

这是多箱装箱问题:

Given a set of items, each of a specific size, and a set of bins, each of a specific size as well – is there a distribution of items to bins such that no item is left unpacked and no bin capacity is exceeded?

一般来说它是 NP-hard。但是，有几种特殊情况可以近似甚至最优地有效解决。

参见 Wolfgang Stille aus Göppingen's thesis