Поиск максимально подходящих множеств

Question

[sionzenit]

Всем доброго утра!
В Java я новичек. Столкнулся с такой задачей:
Есть result = Set[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
И есть множество других Set'ов
A = Set[1, 2, 3, 4, 5, 6, 7, 8]
B = Set[1, 2, 3, 4, 5]
C = Set[1, 2, 3, 4, 5, 6]
D = Set[1, 2, 3, 4, 5, 6, 7]
E = Set[9]
F = Set[10]
J = Set[9, 10]
Задача из множеств найти максимально покрывающие множества, т.е. в результате я должен вернуть только множества A и J.
Подскажите в каком направлении копать? Думаю что тут как-то можно разрулить это дело с помощью containsAll() и size(), но может есть уже какое-то готовое решение или алгоритм?

Comments

[Guran]

Немного не ясно, множества из выборки должны содержать точное количество значений из result, или главное чтобы result покрывался? т.е. есть разница, будь в ответе [1,2,3,4,5,6,7,8],[8,9,10] или [1,2,3,4,5,6,7,8],[9,10]?

[sionzenit]

Да вполне может быть такая ситуация. И может быть ситуация, что не все из result покроется, т.е. [1,2,3,4,5,6,7,8],[9].

Answer 1

[Brand]

en.wikipedia.org/wiki/Set_cover_problem

Answer 2

[metar]

Поиск минимального вершинного покрытия — типичная NP-полная задача, так что можно:
а) смело строчить исчерпывающий поиск и оптимизировать перебор пока не надоест;
б) вдохновиться вот здесь — это алгоритм эффективного перебора для задачи, которая находит все вершины, кроме тех, которые будут в ответе на вашу задачу. :-)