Меня попросили найти 2 приблизительных решения этой проблемы:
Вы консультируетесь по сайту электронной коммерции, который получает большое количество
посетителей каждый день. Для каждого посетителя i, где i € {1, 2 ..... n}, сайт
присвоил значение v [i], представляющее ожидаемый доход, который может быть
получено от этого клиента.
Каждому посетителю показано одно из m возможных объявлений А1, А2.
Войти на сайт. Сайт хочет выбрать одну рекламу для каждого клиента, поэтому
что каждое объявление в целом просматривается группой достаточно крупных клиентов.
общий вес.
Таким образом, учитывая выбор одного объявления для каждого клиента, мы будем
определить спред этого выбора, чтобы быть минимальным, по j = 1, 2 ..... м,
от общего веса всех клиентов, которые были показаны объявление Aj.
Пример. Предположим, есть шесть клиентов со значениями 3, 4, 12, 2, 4, 6 и
Есть m = 3 объявлений. Тогда, в этом случае, можно добиться распространения
9, показывая объявление А1 для клиентов 1, 2, 4, объявление А2 для клиента 3 и объявление А3 для
клиенты 5 и 6.
Конечная цель - найти подборку объявлений для каждого клиента.
что максимизирует спред.
К сожалению, это проблема оптимизации
NP-сложный (вам не нужно доказывать это).
Поэтому вместо этого приведите алгоритм полиномиального времени, который аппроксимирует максимальный разброс с коэффициентом 2.
Я нашел следующее решение:
Order visitors values in descending order
Add the next visitor value (i.e. assign the visitor) to
the Ad with the current lowest total value
Repeat
Это решение, похоже, всегда находит оптимальное решение, или я просто не могу найти контрпример.
Вы можете найти это? Это неполиномиальное решение, и я просто не вижу его?