查找满足多个互斥条件的分组方法 5C

问题:有n个元素a、b、c、d、e、f...,要求将这些元素拆分成m个分组,同时满足条件:集合{a,b,c,d},{b,d,f},{c,e}....内的元素不能在同一个分组。

默认n和m满足分组条件,1个元素可以出现在多个条件集合内;结果不唯一,只要给出1个较优结果,即各个分组内元素数量较均匀。

我的能想到的方法是,先整理出每个元素与其他元素的互斥关系,比如a不能与{b,c,d}在同1分组,b不能与{a,c,d,f}在同1分组...,然后将每个元素互斥条件最多的,从多到少随机分配在m个分组内,每次随机验证是否满足条件,全部随机完成返回结果。

但是这个方法比较暴力,而且不能给出最优解,计算开销也比较大。

求算法大神给个思路或意见。

1个回答

如果是计算最小要分成几组,可以使用拓扑排序,这里分成指定的组数,需要改进下。建议去看看NOIP2013普及复试中的第4题车站分级的问题,或许那里的解题思想可以借用。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问