Учитывая вселенную элементов 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
.
s1 <- set(4, 3, 1)
s2 <- set(3, 1)
s3 <- set(4)
s <- set(s1, s2, s3)
Ура