这被称为垃圾箱包装问题（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 1bag
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三个袋子。
子集总和/背包的问题已经很棘手-如果使用它不能为您提供最佳解决方案，那么您也可以使用上面的排序/贪婪方法。
