Грузовой лифт
Переезд в новый дом. Вещи поднимают грузовым лифтом, который за раз везёт не больше X килограммов, а каждый подъём занимает десять минут, поэтому подъёмов хочется как можно меньше. Вещи не делятся: холодильник едет целиком. Сколько подъёмов понадобится?
Грузчики привыкли ставить в лифт сначала самое тяжёлое, а потом добавлять всё, что ещё помещается. В первом примере это даёт три подъёма, хотя хватает двух.
Вход
В первой строке — n и X (1 ≤ n ≤ 16, 1 ≤ X ≤ 109). Во второй — веса вещей w1, …, wn в килограммах (1 ≤ wi ≤ X).
Выход
Одно число — наименьшее число подъёмов.
Примеры
Пример 1
6 100 40 40 30 30 30 30
2
Пример 2
14 320 72 65 95 38 38 38 38 24 24 24 18 18 12 9
2
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
«Сначала самое тяжёлое» проигрывает в первом примере. Попробуйте перебрать, какие вещи едут вместе. Сколько всего бывает наборов вещей и что о наборе нужно знать?
2Подсказка 2
Пусть вещи набора уже подняты или стоят в лифте. Кроме числа подъёмов, для продолжения важно ещё одно число. Какое? И какое из двух состояний с одним набором лучше?
3Идея
Состояние — маска вещей, которые уже уехали или стоят в текущем подъёме. Для неё храним пару: сколько подъёмов начато и сколько килограммов в последнем. Из двух пар лучше та, у которой меньше подъёмов, а при равенстве — легче последний: в него поместится больше. Переход — добавить вещь i: если она влезает в текущий подъём, вес растёт; если нет — начинается новый подъём с одной этой вещью. Ответ — число подъёмов у полной маски.
4Разбор
Почему хватает одной пары на маску. Любой порядок погрузки — это последовательность вещей, и лифт заполняется по ней жадно: следующая вещь в текущий подъём, если влезает. Лучший ответ получается при каком-то порядке, поэтому достаточно перебрать порядки. А порядки, которые прошли одно и то же множество вещей, различаются для будущего только парой «подъёмов, вес последнего», и пара с меньшим числом подъёмов или, при равенстве, меньшим весом не хуже: любое продолжение для худшей пары даёт для лучшей не больше подъёмов.
Удобный трюк: упаковать пару в одно число подъёмы · (X + 1) + вес. Порядок пар совпадает с порядком чисел, и «лучше» становится обычным «меньше». Масок 216, из каждой до 16 переходов — около миллиона шагов.
В первом примере «сначала тяжёлое» ставит 40 + 40, потом три вещи по 30 и ещё одну отдельно — три подъёма. А можно 40 + 30 + 30 дважды.
4+Решение
5Сложность
O(2n · n) времени и O(2n) памяти. Это задача об упаковке в контейнеры, и в общем случае она NP-трудна: для сотен вещей точного быстрого способа нет, и пользуются как раз правилами вроде «сначала тяжёлое», у которых есть гарантии качества.
6Типичные ошибки
- Сначала самое тяжёлое. Хорошее правило, но не точное: первый пример и четыре скрытых теста.
- Только число подъёмов в состоянии. Тогда не узнать, влезет ли следующая вещь в текущий подъём.
- Хранить все пары для маски. Верно, но лишнее: достаточно одной лучшей, а пар может быть много.