algorithm - 有没有我可以研究这种类似装箱问题的算法？

Question

我正在尝试找到一种方法来解决我认为类似于垃圾箱包装的问题，但据我所知略有不同。就我而言，目标是在每个垃圾箱中装入尽可能多的袋子，而不是使用最少的垃圾箱。也许这是一个最合适的算法？

在我的示例中，我有一个可以容纳多个袋子的数字箱，每个箱只容纳包含特定属性的袋子。每个包可以有许多属性。目标是尽可能多地使用袋子。我觉得可能有一个更好的术语可以用来解决我的问题，但我不确定。

就我而言，每当我必须对它们进行分类时，我都完全了解可用的垃圾箱和袋子。

一个简单的例子

bin 1 allows attribute X with 1 slot
bin 2 allows attribute Y with 1 slot
bin 3 allows attribute Z with 1 slot

1 bag has attribute X, Y and Z
2 bags have attribute X and Y

在这个例子中，很明显 Z 包应该去 bin 3。我最初的想法是循环遍历属性数量最少的 bin 以首先填充它们。

我想知道是否有任何既定的算法可以解决像我这样的问题。

标签： algorithmbin-packing

Answer 1

您希望在可以放置它们的袋子和插槽之间的二分图中进行最大基数匹配。Hopcroft--Karp将有效地完成这项工作。