Определение комбинации вариантов выбора из списка наборов, которая даст максимальное количество уникальных чисел. ⇐ Python

[Anonymous]

У меня есть массив наборов, каждый из которых содержит несколько (уникальных) целых чисел в отсортированном порядке.
Например.
A = {1,2,3>
B = {1,3,4,5,6}
C = {4,5,6,10}

Каждому набору также присваивается соответствующий номер Setx, который меньше количества элементов в наборе, например следующим образом:

Ax = 1
Bx = 4
Cx = 3

Учитывая, что я могу выбрать любую комбинацию элементов Setx из для каждого набора (см. примеры ниже), пусть S — набор всех выбранных (уникальных) элементов и, таким образом, n(S) — количество элементов в S. Тогда n(S)
Например. если я выбираю {1} из A, {1,3,4,5} из B и {4,5,6} из C, то S = {1,3,4,5,6}, n(S ) = 5.
Но выбор {2} из A, {1,3,4,5} из B и {4,6,10} из C дает S = {1,2,3,4, 5,6,10}, n(S) = 7, что кажется максимально возможным.
Дальнейшее расширение:
У каждого числа теперь есть свойство, назовем его звезд и может стоить от 1 до 5 звезд. Например. 1 стоит 5 звезд, 2 стоит 3 звезды. Setx теперь будет общим количеством звезд, которые можно выбрать, т. е. {1,2} можно выбрать из набора D с Dx = 8.< /p>
Мне удалось использовать инструменты Python (как перестановки, так и произведения) для перебора всех возможных комбинаций, однако я ищу более эффективный алгоритм.
Я рассмотрел максимальное покрытие и установил проблемы с покрытием, но, похоже, нигде не нашел этой конкретной проблемы.
Я обдумывал идею определения приоритета выбора от наименее встречающихся чисел к наиболее наиболее встречающиеся числа. Например, сначала выберите 2 и 10, удалите их из наборов и повторите процесс. Однако проблемы возникают, когда наименьшее число встречается в нескольких наборах; или когда имеется несколько наименее встречающихся чисел.
Я также подумал о выборе случайного выбора из первого набора, а затем следующего, таким образом, чтобы все выборы были уникальными, пока точка, в которой невозможно сделать уникальный выбор, а затем возврат к предыдущему набору для изменения его выбора. Однако изменение одного набора за раз не похоже на то, чтобы охватить все случаи, и поскольку у меня нет способа определить максимальное n(S), я не знаю, когда я получил наиболее оптимальное решение.

Подробнее здесь: https://stackoverflow.com/questions/791 ... -yield-the