讨论/算法和数据结构/想到了一道算法题,求大佬们进来留下思路。/
想到了一道算法题,求大佬们进来留下思路。

大概是这个意思,目的是用最少的选择激活全部数字。
比如数字1-9,a选择可以激活[1,2,5,7],b选择可以激活[2,5,6,9],c选择可以激活[3,4],d选择可以激活[0,1,7,9],f选择可以激活[8],e可以激活[4]。
目前有个思路就是每次选择和之前已经选择的交集不同的数字并且最多的,直到剩下选择中的数字都已被涵盖,但感觉复杂度好高,有更好的想法吗。

展开讨论
奔跑中的小新发起于 2020-04-20

不需要求交集吧,每次都取有效激活数目最大的那个选择即可。比如你的题目,一开始,选择a或者b都可以,假设我们选的是a,有效激活数目是4,然后0-9中去除[1,2,5,7],还剩[0,3,4,6,8,9],接下来在剩余的选项中再选择最大有效数目,b选项有2个,c选项有2个,d选项有2个,f和e都是1个,那就选择有效数目最大的那个如果重复就选择第一个符合的选择……以此类推,直至全部找完。

展开全部 3 讨论