CS
Задачник Базовый курс EN

Задача

Кому какой заказ

динамика битовые трюки оптимизация паросочетания логистика

В диспетчерской службе доставки n свободных курьеров и n новых заказов. Каждому курьеру нужно отдать ровно один заказ, и каждый заказ должен достаться кому-то одному. Для каждой пары известно, сколько метров курьеру ехать до заказа по дорогам. Как распределить заказы, чтобы курьеры вместе проехали как можно меньше?

Диспетчер привык давать каждому следующему курьеру ближайший к нему из оставшихся заказов. В первом примере это стоит лишних 400 метров. В тестах есть настоящие расстояния по улицам Алматы.

Вход

В первой строке — n (1 ≤ n ≤ 16). Дальше n строк по n целых чисел: j-е число в i-й строке — сколько метров курьеру i до заказа j (0 ≤ число ≤ 106).

Выход

Одно число — наименьший суммарный путь в метрах.

Примеры

Пример 1

Вход
2
300 500
400 1000
Выход
900

Пример 2

Вход
4
9016 6428 10241 12160
8299 7953 4572 9492
10458 1812 4409 12842
8032 9107 5887 7446
Выход
22846

Ограничения

Время · Python
2000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
9 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Перебор всех распределений — 16! ≈ 2 · 1013 вариантов. Что нужно знать о частично распределённых заказах, чтобы решать дальше? Важно ли, кому именно достались уже отданные заказы?

2Подсказка 2

Отдавайте заказы курьерам по очереди: первому, второму, третьему… Тогда по множеству уже отданных заказов видно и то, какой курьер следующий.

3Идея

Состояние — маска отданных заказов. Если в маске k единиц, то заказы получили курьеры 0, 1, … , k − 1, и следующий — курьер k. best[mask] — наименьший суммарный путь при таком распределении; переход — отдать курьеру k любой свободный заказ j: best[mask | 2j] ← best[mask] + cost[k][j]. Ответ — best полной маски. Это динамика по маскам, а номер курьера не нужен в состоянии: его даёт число единиц маски.

4Разбор

Почему так можно: для будущих курьеров важно только, какие заказы ещё свободны, а не кто и как взял остальные. Из всех способов раздать заказы маски первым k курьерам достаточно помнить самый дешёвый — любой более дорогой с тем же остатком можно заменить на него.

Маски перебираются по возрастанию: переход только добавляет бит, и маска растёт, поэтому к моменту обработки маски все пути в неё уже учтены. Состояний 216 = 65 536, из каждого не больше 16 переходов — около миллиона операций.

Во втором примере четыре курьера и четыре заказа на настоящих улицах Алматы: привычка «каждому ближайший» даёт 28 904 метра, а лучшее распределение — 22 846. На шестнадцати курьерах из тестов привычка проигрывает до пятой части пути.

4+Решение
5Сложность

O(2n · n) времени и O(2n) памяти. Для больших n эту задачу о назначениях решают венгерским алгоритмом — его опубликовал Гарольд Кун в 1955 году, а в более поздних вариантах он работает за O(n³). Маски хороши, пока n до двадцати, и тогда, когда к задаче добавляются условия, которые венгерскому алгоритму не выразить: например, что двое курьеров не берут заказы в одном районе.

6Типичные ошибки
  • Каждому курьеру ближайший свободный заказ. Не проходит первый пример: 300 + 1000 вместо 500 + 400.
  • Номер курьера в состоянии. best[mask][i] верно, но в n раз больше, чем нужно: курьер и так определяется маской.
  • Перебор перестановок. 16! вариантов не перебрать ни за какое разумное время.

Алгоритмы задачи

DP Приём Динамика по маскам Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю. O(2ⁿ · n²) для коммивояжёра 2 задачи TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача
Каталог алгоритмов