背包有多个袋子和只有重量的物品

Question

我试图解决这个问题,我想知道是否有已知的现有算法/解决方案来解决这个问题.

问题:

我有n个袋子和n个物品(可以是相同或不同的重量)来装入这些袋子.这些袋中的每一个都具有一定的重量限制,并且需要将n个物品放入这些袋中,使得我可以使用每个袋中的最大空间.

袋子大小相同.还想知道如何解决不同尺寸的包袋.

我读过的大部分解决方案都试图解决一个重量和价值都在0/1的背包.我应该考虑重量和价值吗？我是在正确的轨道上吗？

这不是一个家庭作业问题.

Answer 1

这被称为垃圾箱包装问题(NP-hard).

通过简单地按递减顺序对降序进行排序,然后将每个项目插入列表中具有足够剩余空间的第一个bin中,我们得到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每个袋子.

子集和/背包已经是一个难题 - 如果使用它不会给你一个最佳解决方案,你也可以使用上面的排序/贪婪方法.