给定一个元素U = {1,2,3,...,n}的宇宙以及这个宇宙中的许多集合{S1,S2,...,Sm},我们可以创建的最小集合是什么覆盖m组中的每一组中的至少一个元素？
例如,给定以下元素U = {1,2,3,4}并设置S = {{4,3,1},{3,1},{4}},以下几组将涵盖至少一个每组中的元素:{1,4}或{3,4}所以此处所需的最小大小为2.
有关如何扩大规模以解决m = 100或m = 1000套问题的任何想法？或者想一想如何用R或C++编写代码？
上面的样本数据使用R' library(sets).
s1 <- set(4, 3, 1)
s2 <- set(3, 1)
s3 <- set(4)
s <- set(s1, s2, s3)
干杯