У меня есть база данных N рекламных щитов, в которой указаны идентификаторы всех людей, которые видели каждый рекламный щит.Мне нужно найти рекламные щиты k, которые видели наибольшее количество уникальных людей среди рекламных щитов k.
Например:
- У меня
N = 3 рекламные щиты: рекламный щит 1 видели люди 'a', 'b' и 'c', рекламный щит 2 видели люди 'b' и рекламный щит 3 видели люди 'c' и 'd' k = 2- Решение - рекламные щиты 1 и 3, которые вместе видели четыре человека (
'a', 'b', 'c' и 'd')
Таким образом, каждый рекламный щит представляет набор значений, и мне нужно найти k рекламных щитов из N, которые имеют наибольшее количество уникальных значений.
Я не могу сделать это с помощью грубой силыиз-за огромного количества потенциальных комбинаций (> 10 000 рекламных щитов в моей базе данных), существует ли алгоритм, который быстрее найдет оптимальное или почти оптимальное решение ?Скорость здесь важнее, чем получить правильный ответ.
Предпочтительно я также хотел бы иметь возможность ограничить алгоритм так, чтобы сумма затрат на выбранные рекламные щиты была ниже определенного значения, хотя это не является строго обязательным.
IЯ думаю, что это похоже на некоторые из комбинаторных задач оптимизации, описанных здесь , в частности, задачу о ранце здесь , за исключением того, что эти задачи работают с наборами чисел, а не с наборами множеств,Мои математические навыки отрывочны, поэтому я не смог понять, могу ли я изменить эти уравнения в соответствии со своими потребностями.
Спасибо