多背包问题中，物品只有重量，如何解决？

Question

多背包问题中，物品只有重量，如何解决？

algorithmknapsack-problem

12

我正在尝试解决这个问题，并想知道是否有已知的算法/解决方案可以解决这个问题。

问题：

我有n个袋子和n个物品（它们的重量可能相等也可能不同）需要放入这些袋子中。每个袋子都有一定的重量限制，并且需要以这样的方式将n个物品放入这些袋子中，以便我可以在每个袋子中使用最大的空间。

袋子大小相同。还想知道如何处理大小不同的袋子。

我阅读的大多数解决方案都试图解决具有权重和价值的0/1背包。我应该将重量和价值视为相同吗？我走对了吗？

这不是一个作业问题。

- Jony

这些袋子大小一样吗？ - JensG

这不应该等同于将剩余物品装入 1 至 N-1 号袋子后剩下的物品填满第 N 号袋子的问题吗？大小不相等可能会更加困难。 - JensG

我应该把重量和价值视为相同吗？ - Jony

您是否试图使用最少数量的袋子（每个袋子的最大空间有些不清楚）？ - Bernhard Barker

最小化袋子优先？“每个袋子中的最大空间”指的是什么？您可能不想只填满一个袋子而不关心其他袋子。您希望将最小值尽可能提高吗？还是平均值（这将与最小袋子完全相同）？ - Bernhard Barker

显示剩余6条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

这被称为装箱问题（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.2^{maxItemsPerBag})。

在只有一个包的情况下，这实际上是子集和问题。对于此问题，可以将重量视为价值并使用背包算法进行解决，但对于多个包来说并不会起作用。

为什么呢？考虑物品5,5,5,9,9,9和包大小16。如果你只是解决子集和，你会得到每个包中分别是5,5,5和9的结果（总共4袋），而不是每个3个包中都是5,9。

子集和/背包已经是一个困难的问题 - 如果使用它不能给你最优解，那么你可以使用上面的排序/贪心方法。