Максимально накрывающий набор из k элементов

Question

Учитывая совокупность элементов U = {e_1 .... e_n}, у меня есть коллекция подмножеств этих элементов C = {s_1 ... s_m}.Теперь, учитывая положительное целое число k, я хочу найти решение k элементов, которые охватывают максимальное количество подмножеств.

Конкретный пример: у меня есть коллекция песен.каждая песня состоит из нот.если я знаю только, как играть k разных нот - какие k нот позволят мне воспроизвести максимальное количество песен и каково это максимальное число?

Как называется эта проблема?

Answer 1

Подход с помощью грубой силы:

Сначала найдите все отличные перестановки размера k от n.Затем для каждой найденной перестановки число подмножеств, которые оно покрывает.И помните, если вы берете один элемент, который охватывает подмножество 's_1', например, тогда вы должны взять все элементы из этого подмножества, иначе жадный подход охватит только некоторую часть подмножества, а не целое.А затем выберите ту перестановку, которая дает максимальный ответ.

Но метод грубой силы работает только тогда, когда k меньше 10. Поскольку порядок идет экспоненциально, и нет лучшего решения, чем этот, таким образом, этот вопрос переходит к np_hard.Можно показать, что эта проблема сводится к проблеме покрытия вершин.

Рассматривать подмножества как деревья, а элементы как узлы.Теперь ваша проблема состоит в том, чтобы выбрать k элементов так, чтобы они полностью покрывали максимальное количество деревьев.