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

Диски для аудиокниги

перебор с возвратом ветви и границы оптимизация

Аудиокнигу издают на компакт-дисках. На диск помещается C минут — у обычного диска это 80. Главу нельзя разрезать между дисками, а порядок глав на дисках для издателя неважен: на обложке будет список. Сколько дисков понадобится, если раскладывать главы как можно экономнее? В тестах есть настоящие части «Войны и мира», где длительность главы — время чтения при 150 словах в минуту.

Вход

В первой строке число глав n и вместимость диска C в минутах (1 ≤ n ≤ 20, 1 ≤ C ≤ 100). Во второй — длительности n глав, целые от 1 до C.

Выход

Наименьшее число дисков.

Примеры

Пример 1

Вход

13 80
17 38 35 25 12 39 25 11 31 17 30 11 25

Выход

Ограничения

Время · Python: 5000 мс
Время · Go: 1500 мс
Память: 256 МБ
Проверка: 12 тестов

Разбор

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

1Подсказка 1

Известный способ — «первый подходящий по убыванию»: главы от длинных к коротким, каждую — на первый диск, где хватает места, а если такого нет, на новый. Сколько дисков он даёт на примере? А сколько нужно на самом деле?

2Подсказка 2

На примере жадный способ кладёт 39 + 38 на первый диск, и три минуты на нём пропадают. Нужен перебор: каждую главу пробуем на каждый открытый диск и на новый. Какие ветки можно не открывать?

3Идея

Те же отсечения, что в статье, только рекорд — число дисков. Начинаем с ответа жадного способа. Ветку отсекаем, если дисков уже не меньше рекорда; если места на открытых дисках и на тех, что ещё можно открыть, не хватит на оставшиеся главы; главу не пробуем на двух дисках с одинаковой записью — это одна и та же ветка; новый диск открываем один, а не на каждое пустое место. И останавливаемся, когда рекорд дошёл до нижней оценки.

4Разбор

Нижняя оценка здесь двойная. Первая — ⌈сумма / C⌉: дисков не меньше, чем требует общая длина. Вторая — число глав длиннее половины диска: две такие главы на один диск не лягут, так что каждой нужен свой. Берём большую из двух. На тесте, где все главы длиннее половины диска, первая оценка равна 4, а ответ — 5, и вторая оценка позволяет остановиться сразу.

Порядок «сначала длинные» важен вдвойне: длинные главы труднее всего пристроить, и тупики обнаруживаются на малой глубине, а короткие в конце почти всегда находят себе место, и запас быстро доказывает, что лучше не будет.

Задача об упаковке в контейнеры трудна, и гарантий у перебора нет. Жадный способ, наоборот, гарантию даёт: ему нужно не больше 11/9 от наименьшего числа дисков плюс небольшая постоянная — но, как видно на тестах, лишний диск бывает уже на десятке глав.

4+Решение

5Сложность

В худшем случае экспоненциально; на тестах — от одного узла до нескольких тысяч, доли секунды даже на Python.

6Типичные ошибки

Жадность. На шести тестах из двенадцати ей нужен лишний диск, в том числе на примере.
Новый диск на каждое место. Если при переборе пробовать положить главу «на второй пустой диск», «на третий пустой» и так далее, дерево размножается на одинаковые ветки. Пустые диски неразличимы, и открывать нужно один.
Только оценка по сумме. Ответ остаётся верным, но остановиться на оценке удаётся реже, и перебору приходится доказывать оптимальность обходом.

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

TEC Приём Отсечения Не открывать ветки, где заведомо нет ответа лучше: рекорд, порядок, симметрия, оценки снизу. O(kⁿ) в худшем случае 2 задачи PAR Приём Ветви и границы 38 аэропортов, где из каждого прямой рейс в каждый: оценка раскраской сжимает перебор с миллиона узлов до 242. экспоненциальное в худшем случае 1 задача