用于找到最少数量的子集的算法加起来等于原始集合

Question

我有一个原始集（1、2、3、4、5、6）我有一组列表：[（（1,2,3），（1,4），（1），（1,4,5,6），（2,4,6）]我需要在列表中找到添加到原始集合中的子集最少。在这种情况下，答案是2。

我已经尝试了蛮力方法，但对于我的解决方案来说太慢了。有人可以帮助我提供更有效的解决方案吗？

Answer 1

解决此问题的最佳算法是递归。

每次您都会在列表中找到最大的子集，将其从原始集中减少，然后解决相同的问题，但是使用较小的原始集中，将重复此操作，直到原始集中没有成员为止。

简单的逐步sudo代码：

1. 制作一个字典，将所有原始集合成员配对为“ True”
2. 遍历子集列表，找到具有最大真实成员数的子集。 （基本上找到最大的子集）称为最大子集
3. 更新集合（字典）：遍历max子集，并将其成员的值在字典中更改为False。 （从技术上讲，这意味着我们将从原始集中删除这些成员）
4. 循环应继续进行，直到字典中的所有键都为假。 （原始集为空），然后计算在每个递归步骤中找到的最大子集数。 （或者基本上是重复循环的次数）

---

我在这里不会证明为什么该算法正确。它比编码要复杂得多。

PS：循环可以是调用自身的函数，也可以是while循环。

编辑：

我先将字典称为地图，所以犯了一个错误。原因是在java map中做同样的事情。我编辑了答案。我也写了这段代码作为提示：

k = {} #empty dictionary
list1 = [1,2,3,4,5] #original set

#Making the dictionary 
for i in list1:
    k[i] = True

print(k)
#{1: True, 2: True, 3: True, 4: True, 5: True}

#Updating the dictionary based on elements on maxSub

maxSub = [2,3,5]
for i in maxSub:
    k[i] = False
print(k) 
#{1: True, 2: False, 3: False, 4: True, 5: False}