背负式多袋物品只具有重 [英] Knapsack with multiple bags and items having only weight

问题描述

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

问题：

  

我有n个包和n项（这是相等或不同的权重），以填补到这些袋子。每个这些袋子具有一定的重量限制和n个项目需要被放入这些袋子中，我可以使用的最大空间中的每个这些袋子这样一种方式

袋子大小相等。会也想知道如何解决与包大小不等太。

大多数我看了试图解决一个0/1背包与重量和价值的解决方案。我应该考虑的重量和价值一样吗？我是在正确的轨道？

这是不是一个家庭作业的问题。

解决方案

这就是所谓的的装箱问题（这是一个NP难）。

通过简单的排序从大到小依次通过它们的大小，然后将每个项目进入第一仓在列表中有足够的剩余空间，我们得到 11/9 OPT + 6/9 箱（其中 OPT 是最佳的解决方案中使用回收箱的数量）。这将轻松拍摄 O（N²），或可能是为O（n log n）的与一个有效的实施。

在最优的解决方案方面，有没有那么的AS众所周知作为背包问题动态规划的解决方案。 此资源有一个选项 - 基本思想是

  D [{设定}] =在使用每个项目袋的最小数量{设定}

然后：

D [{设置1}] =最小的所有D [{设置1}  -  {设定2}]，其中设置2适合1包
                                                  是集1的一个子集
 

     

以上的数组索引是名副其实的集 - 认为这是集合的映射值，位图或多维数组，其中每个指标为1或0，表明我们是否包含对应于三维项目或不

     

链接的资源实际上考虑多种类型，它可以发生多次 - 我来自的是，上述解决方案

。      

运行时间将大大取决于可以放入袋内物品的数量 - 这将是 0（minimumBagsUsed.2 maxItemsPerBag ）。

在1包的情况下，这基本上是的子集和问题的。对于这一点，你可以考虑重量相同的价值，解决使用背包算法，但是这不会真的工作了好多个包。

为什么不呢？考虑用一个书包大小的物品 5,5,5,9,9,9 16 。如果你只是解决了一部分款项，留给你 并在一5,5,5制袋于一体 9 每包（总共 4 袋），而不是 5.9 在每3袋。

子集和/背包已经是一个棘手的问题 - 如果使用它不会给你一个最佳的解决方案，您不妨使用上面的排序/贪婪的方法

。

I am trying to solve this problem and I wanted to know if there are known existing algorithms / solutions to solve this.

Problem:

I have n bags and n items (which are either equal or different weights) to fill into these bag. Each of these bags have a certain weight limit and the n items needs to be put into these bags in such a way that I can use the maximum space in each of these bags.

The bags are of equal size. Will also like to know how to solve with bags of unequal size too.

Most of the solutions I read was trying to solve a 0/1 knapsack with a weight and value. Should I consider the weight and value as same? Am I on the right track?

This is not a homework problem.

解决方案

This is known as the bin packing problem (which is NP-hard).

By simply sorting the decreasing order by their sizes, and then inserting each item into the first bin in the list with sufficient remaining space, we get 11/9 OPT + 6/9 bins (where OPT is the number of bins used in the optimal solution). This would easily take O(n²), or possibly O(n log n) with an efficient implementation.

In terms of optimal solutions, there isn't a dynamic programming solution that's as well-known as for the knapsack problem. This resource has one option - the basic idea is:

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

The array index above is literally a set - think of this as a map of set to value, a bitmap or a multi-dimensional array where each index is either 1 or 0 to indicate whether we include the item corresponding to that dimensional or not.

The linked resource actually considers multiple types, which can occur multiple times - I derived the above solution from that.

The running time will greatly depend on the number of items that can fit into a bag - it will be O(minimumBagsUsed.2maxItemsPerBag).

In the case of 1 bag, this is essentially the subset sum problem. For this, you can consider the weight the same as value and solve using a knapsack algorithm, but this won't really work too well for multiple bags.

Why not? Consider items 5,5,5,9,9,9 with a bag size of 16. If you just solve subset sum, you're left with 5,5,5 in one bag and 9 in one bag each (for a total of 4 bags), rather than 5,9 in each of 3 bags.

Subset sum / knapsack is already a difficult problem - if using it's not going to give you an optimal solution, you may as well use the sorting / greedy approach above.

这篇关于背负式多袋物品只具有重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！