我正在尝试解决这个问题,并想知道是否有已知的算法/解决方案可以解决这个问题。
问题:
我有n个袋子和n个物品(它们的重量可能相等也可能不同)需要放入这些袋子中。每个袋子都有一定的重量限制,并且需要以这样的方式将n个物品放入这些袋子中,以便我可以在每个袋子中使用最大的空间。
袋子大小相同。还想知道如何处理大小不同的袋子。
我阅读的大多数解决方案都试图解决具有权重和价值的0/1背包。我应该将重量和价值视为相同吗?我走对了吗?
这不是一个作业问题。
我正在尝试解决这个问题,并想知道是否有已知的算法/解决方案可以解决这个问题。
问题:
我有n个袋子和n个物品(它们的重量可能相等也可能不同)需要放入这些袋子中。每个袋子都有一定的重量限制,并且需要以这样的方式将n个物品放入这些袋子中,以便我可以在每个袋子中使用最大的空间。
袋子大小相同。还想知道如何处理大小不同的袋子。
我阅读的大多数解决方案都试图解决具有权重和价值的0/1背包。我应该将重量和价值视为相同吗?我走对了吗?
这不是一个作业问题。
这被称为装箱问题(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)
。在只有一个包的情况下,这实际上是子集和问题。对于此问题,可以将重量视为价值并使用背包算法进行解决,但对于多个包来说并不会起作用。
为什么呢?考虑物品
5,5,5,9,9,9
和包大小16
。如果你只是解决子集和,你会得到每个包中分别是5,5,5
和9
的结果(总共4
袋),而不是每个3个包中都是5,9
。子集和/背包已经是一个困难的问题 - 如果使用它不能给你最优解,那么你可以使用上面的排序/贪心方法。
5,5,5,9,9,9
,背包大小为 16
。如果你只解决子集和问题,你会得到一个袋子里有 5,5,5
,另一个袋子里有 9
的结果(总共 4
个袋子),而不是每个袋子里都有 5,9
。背包问题本来就很难 - 如果使用它不能给你最优解,那么你可能还不如使用答案中提到的贪心方法。 - Bernhard Barker9,9,9,5,5,5
。然后将3个9一个接一个地放入单独的袋子中(因为它们不能放在同一个袋子里)。然后插入5 - 第一个5和9一起放进第一个袋子里,所以它放在那里。第二个5不能放在第一个袋子里,但能放在第二个袋子里。第三个5无法放入前两个袋子中,因此放入第三个袋子中。因此我们最终得到了每个袋子中的 5,9
。 - Bernhard Barker
1
至N-1
号袋子后剩下的物品填满第N
号袋子的问题吗?大小不相等可能会更加困难。 - JensG