这被称为垃圾箱包装问题（NP难题）。

通过简单地按其大小对降序进行排序，然后将每个项目插入列表中具有足够剩余空间的第一个垃圾箱中，就可以得到11/9 OPT + 6/9垃圾箱（其中OPT是最佳解决方案中使用的垃圾箱数）。这很容易实现O(n²)，或者可能O(n log n)具有有效的实现。

就最佳解决方案而言，没有一个背包问题众所周知的动态编程解决方案。该资源有一个选项-基本思想是：

D[{set}] = the minimum number of bags using each of the items in {set}

Then:

D[{set1}] = the minimum of all D[{set1} - {set2}] where set2 fits into 1

bag
and is a subset of
set1

上面的数组索引实际上是一个集合-可以将其视为集合到值的映射，位图或多维数组，其中每个索引为1或0以指示我们是否包括与该维度相对应的项。

链接的资源实际上考虑了多种类型，这些类型可以多次出现-我从中得出了上述解决方案。

运行时间将在很大程度上取决于可放入袋子的物品的数量-它将是多少。O(minimumBagsUsed.2maxItemsPerBag)

在1袋的情况下，这本质上是子集和问题。为此，您可以将重量与值视为相同，并使用背包算法求解，但是对于多个袋子来说，这实际上并不是很好。

为什么不？考虑5,5,5,9,9,9袋子大小为的物品16。如果只解决子集和，则剩下的只有5,5,5一个袋子，9每个袋子一个（总共4袋子），而不是5,9三个袋子。

子集总和/背包的问题已经很棘手-如果使用它不能为您提供最佳解决方案，那么您也可以使用上面的排序/贪婪方法。