#algorithm #sorting #variable-assignment
#алгоритм #сортировка #переменная-назначение
Вопрос:
Мне нужно написать алгоритм (псевдокод подходит) для решения следующей проблемы.
У нас есть список продуктовых магазинов супермаркета, скажем, 3000. У нас есть рейтинг footfall для каждого хранилища от 1 до 3000. Хранилища идентифицируются по номерам индексов.
У нас есть несколько списков магазинов (все из которых являются членами основного списка из 3000 выше) для различных маркетинговых кампаний, которые мы хотим запустить; в каждом магазине может быть представлена только одна кампания. Задача состоит в том, чтобы распределить маркетинговые кампании по магазинам таким образом, чтобы:
- каждая кампания получает как можно больше магазинов из требуемого списка.
- кампании получают наилучший возможный рейтинг посещаемости, а лучшие магазины посещаемости распределяются между кампаниями максимально справедливо
Может быть выделено до 10 маркетинговых кампаний, и между ними может быть любое количество совпадений.
Я уже создал один алгоритм, показанный ниже. Это успешно работает для выравнивания ранжирования по посещаемости, но поскольку он проходит по списку магазинов в порядке следования, возможно, что у нас закончатся магазины, не удовлетворив весь спрос.
Текущий метод заключается в следующем:
- Расположите список основного хранилища в порядке следования
- Расположите список кампаний в порядке приоритета (это мало что меняет, но в любом случае)
- Возьмите список кампаний (1) — есть ли в нем все необходимые хранилища? Если да, перейдите к следующей кампании и повторите. Если нет, является ли это хранилище членом списка кампаний (1)? Если это так, выделите кампанию 1 для этого хранилища, перейдите в следующее хранилище. Если нет, перейдите к следующей кампании и вернитесь к началу шага 3.
- Повторяйте, пока не будут распределены все кампании или у вас не закончатся магазины.
Этот метод обеспечивает идеальную долю посещаемости для разных кампаний, но поскольку совпадение между любым заданным списком кампаний и основным списком магазинов различно для каждой кампании, у кампании могут закончиться магазины до того, как она получит все магазины, которые она хотела, даже если их достаточно — просто недостаточно, когда вы просматриваете их в порядке следования, распределяя их поровну, как это делает этот метод.
Код не имеет значения, поскольку я переведу правильный поток в JS.
Ожидаемый результат с использованием текущего алгоритма:
Представьте, что кампании 1 и 2 обе хотят иметь 100 магазинов. Мы строим диаграмму Венна, показывающую, что существует достаточно хранилищ, чтобы удовлетворить 100 хранилищ для каждого из 1 и 2, учитывая все перекрытия.
Желаемый результат: каждой кампании выделяется 100 магазинов. Ранг шага выравнивается, насколько это возможно, с учетом распределения.
Фактический результат: кампания 1 получает 100 магазинов, кампания 2 получает 84 магазина, рейтинг посещаемости идентичен.
Глядя на вывод Excel, можно поменять местами магазины с 1 на 2 таким образом, чтобы 2 получили 100 магазинов, а 1 смог пополнить запасы из магазинов, которые могут нести только кампанию 1. Ранжирование шагов немного отличается.
Комментарии:
1. как вы вычисляете рейтинг посещаемости набора хранилищ?
2. Вы подсчитываете количество покупателей, входящих в данный период времени. Но для целей этого упражнения это не имеет значения. Просто предположим, что в главном списке хранилища у нас есть ранг footfall, и это точно. 🙂
3. Я имею в виду, что вы запрашиваете кампании, чтобы получить наилучший возможный рейтинг посещаемости, но все, что я знаю, — это один рейтинг магазина, как вы вычисляете рейтинг кампании? Просто сумма его хранилищ? Также «каждая кампания получает как можно больше магазинов из своего требуемого списка». требуется более формальное определение. Вы хотите максимизировать наименьшее количество магазинов, которые получает кампания из требуемого? Или вы хотите максимизировать среднее значение?
4. Каждое хранилище имеет рейтинг от 1 до 3000. Показатель посещаемости кампании определяется как среднее значение показателей посещаемости всех ее магазинов. Я хочу максимизировать количество магазинов, которые кампания получает из своего требуемого списка (приоритет 1), при этом, насколько это возможно, гарантируя, что все кампании имеют одинаковый рейтинг лучшей посещаемости (приоритет 2)
5. Вы можете смоделировать это как задачу оптимизации, но ваша цель того, что вы хотите оптимизировать, неясна (математически). Если вы моделируете это как задачу оптимизации, вы можете использовать решатель и получить точный ответ. Если нет, вы просто ищете эвристику