从"x“组植物到"y”篮子中的物品平均分布
从"x“组植物到"y”篮子中的物品平均分布
提问于 2010-04-07 19:06:58
我需要关于分组分配植物的算法的想法。我有，比方说，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“个篮子中一个接一个地开始分布，那么在大多数情况下，最后一个分布将是唯一有效的，即篮子中将有均匀的花朵分布，但不一定有水果，根或颜色等。
如何均匀地分配所有这些资源？有什么想法吗？
回答 1
Stack Overflow用户
发布于 2011-02-01 08:14:50
这是maximum match problem in a bipartite graph的一个变体。
例如，你有20株植物和5组植物。然后，第一组节点将由20个植物和另一个-5个篮子组成，但每个篮子将呈现4次(也是总共20个节点)。
现在，你只需要将20株植物与20个篮子节点进行匹配，这就是上面的问题。
如果n不能被m整除，您可以添加一些备用总线节点。例如，如果是n = 23和m = 5，则每个篮子可以重复5次。当找到完美匹配时，总线集仍将有两个(5*5 - 23)空闲节点。
为了让“几乎相等”的需求更好地工作(当没有完美匹配的时候)，你可以让图加权。即，greenPlantsBasket#1成本为1，greenPlantsBasket#2成本为2，greenPlantsBasket#3成本为4，等等。
维基百科为所有类型的最大匹配问题提供了算法，也有实现库。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2591841
复制相关文章
相似问题
腾讯云开发者
