有没有什么算法可以解决这个像装箱这样的问题？

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，先填充它们。

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

Answer 1

我不确定具有 X、Y 和 Z 属性的袋子是否应该放入 Bin Z。如果您有 50 个只有属性 Z 的袋子怎么办？可能我没有完全理解问题...

假设我理解正确，您希望垃圾箱之间均匀分布。

Sort by number of attributes

if (1 attribute) 
    place in matching bin
else
    place in matching bin with lowest count

虽然这不是一个完美的解决方案，但我认为它可以帮助您入门...也许对每个垃圾箱再次使用相同的算法，将垃圾箱从最高计数到最低计数排序。

Answer 2

当然可以。查看：

Divide and Conquer：它的基础是将你的复合问题分成更小但相似的子问题，直到你达到琐碎程度
Backtracking: 尝试每一种可能性，完成后比较结果（完美，但很慢）
Dynamic Pogramming

Answer 3

您希望 maximum cardinality matching in the bipartite graph between bags and slots where they can be placed. Hopcroft--Karp 能够高效地完成工作。

有没有什么算法可以解决这个像装箱这样的问题？

Is there any algorithms I can look into for this bin-packing like problem?

algorithm

bin-packing