algorithm - 将 "x"组植物中的元素平均分配到 "y"篮子中

Question

我需要有关植物分组分布算法的想法。我有 5 组植物，每组都描绘了特定的属性，例如，

setA= {set of all plants that are green in color} 

setB = {set of all plants red in color} 

setC={ all the plants that are roots also} 

setD= {fruits} 

setE= [flowers}

一个植物可以是多个集合的成员。植物的总数是“n”，我有“m”个篮子。需要做的是将所有这些“n”株植物分布在“m”个篮子中，这样对于每组，所有篮子中的植物数量都相等(或几乎相等)。问题来了。如果我开始为每组一个一个地分配“m”个篮子，那么在大多数情况下，最后一个分配将是唯一有效的，即篮子里均匀分布着鲜花，但不一定是水果、根或颜色等。

如何平均分配所有这些？有什么想法吗？

Answer 1

这是 maximum match problem in a bipartite graph 的变体.

例如，您有 20 个植物和 5 个组。然后，第一组节点将包含 20 株植物，另一组节点包含 5 个篮子，但每个篮子将出现 4 次(总共也有 20 个节点)。
现在，您只需将 20 株植物匹配到 20 个篮子节点，这正是上面的问题。

如果 n 不能被 m 整除，您可以添加一些备用总线节点。例如，如果 n = 23 和 m = 5，您可以将每个篮子重复 5 次。当找到完美匹配时，busket-set 仍将有两个 (5*5 - 23) 个空闲节点。

为了使“几乎相等”的要求更好地发挥作用(当没有完美匹配时)，您可以改为对图表进行加权。即，greenPlantsBasket#1 花费 1，greenPlantsBasket#2 花费 2，greenPlantsBasket#3 花费 4，等等。

维基百科提供了各种最大匹配问题的算法，也有实现库。