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

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

展开讨论
共 3 个讨论

状态压缩,用二进制数记录每个数有没有被取到,然后DP。贪心肯定是有反例的。话说这题力扣上有,1125.最小的必要团队

1

每个数字对应到的字母列出来,唯一的字母就必须选中吧,剩下的组成树来做深度遍历?

不需要求交集吧,每次都取有效激活数目最大的那个选择即可。比如你的题目,一开始,选择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个,那就选择有效数目最大的那个如果重复就选择第一个符合的选择……以此类推,直至全部找完。