Задача упаковки в контейнеры
При переезде вы заполняете одну коробку за другой и думаете, не понадобилось бы меньше коробок при более умном порядке. Это и есть задача упаковки в контейнеры, и она известна своей сложностью: даже компьютеры находят наименьшее число контейнеров для больших входных данных лишь с помощью хитрого перебора. Зато простые правила подходят к ответу удивительно близко.
Задача
Даны предметы с размерами и контейнеры одинаковой вместимости. Нужно разложить все предметы по контейнерам так, чтобы ни один контейнер не переполнился, и использовать как можно меньше контейнеров. Размеры могут означать вес, длину, длительность или размер файлов. Звучит как головоломка на дождливый вечер, но задача NP-трудна: не известно метода, который быстро находит наименьшее число контейнеров для любых входных данных.
Быстрые правила
«Следующий подходящий» заполняет один контейнер, пока очередной предмет не перестанет помещаться, затем начинает новый и больше не возвращается. «Первый подходящий» держит все контейнеры открытыми и кладет каждый предмет в первый контейнер, где есть место. «Наилучший подходящий» кладет каждый предмет в самый заполненный контейнер, где еще есть место. Все три решают сразу, что удобно, когда предметы приходят по одному и их нужно размещать немедленно.
Сначала сортировка
Трудные предметы — большие: им нужно много свободного места. Если отсортировать предметы от больших к маленьким и затем применить «первый подходящий» или «наилучший подходящий», большие предметы попадут в контейнеры, пока те еще пустые, а промежутки заполнят маленькие. «Первый подходящий по убыванию» никогда не использует больше 11/9 от наименьшего числа контейнеров плюс константа, тогда как у «первого подходящего» на неотсортированных предметах этот множитель равен 1,7.
Пример
Возьмем контейнеры размера 10 и предметы 2, 3, 2, 1, 3, 4, 5, 6, 7 и 7, в сумме 40. «Первый подходящий» кладет 2, 3, 2 и 1 в первый контейнер, 3 и 4 — во второй, а затем каждому из предметов 5, 6, 7 и 7 нужен отдельный контейнер: всего 6 контейнеров. После сортировки по убыванию «первый подходящий по убыванию» составляет 7 + 3, 7 + 3, 6 + 4 и 5 + 2 + 2 + 1: 4 полных контейнера, что совпадает с нижней границей 40 / 10 = 4.
Как найти наименьшее число контейнеров
Для небольшого числа предметов точный ответ можно найти динамическим программированием по подмножествам: для каждого множества предметов наименьшее число контейнеров и самый пустой последний контейнер, которые его вмещают, строятся из множеств на один предмет меньше. Это занимает около 2ⁿ·n шагов для n предметов. Более крупные задачи решают методом ветвей и границ или целочисленным программированием, а нижняя граница показывает, насколько упаковка может отличаться от лучшей.
Где это применяется
Загрузка грузовиков и контейнеров, раскрой труб или рулонов бумаги стандартной длины с минимальными отходами (задача раскроя), размещение виртуальных машин на серверах и запись файлов на диски — все это задачи упаковки в контейнеры. В двух и трех измерениях, с коробками вместо чисел, задача еще труднее.
Часто задаваемые вопросы
Чем онлайн-упаковка отличается от офлайн-упаковки?
В онлайн-варианте каждый предмет нужно разместить сразу, как только он пришел, не зная остальных; так работают «следующий подходящий», «первый подходящий» и «наилучший подходящий». В офлайн-варианте все предметы известны заранее, поэтому их можно сначала отсортировать, как это делает «первый подходящий по убыванию».
Насколько близок к оптимуму «первый подходящий по убыванию»?
Он использует не больше 11/9 от наименьшего числа контейнеров плюс 6/9 контейнера; в 2007 году Дьёрдь Доша доказал, что эта оценка точная. На типичных входных данных он обычно оптимален или ошибается на один контейнер.
Упаковка в контейнеры — это то же самое, что задача о рюкзаке?
Они связаны, но различаются. В задаче о рюкзаке один рюкзак заполняют самыми ценными предметами; при упаковке в контейнеры все предметы раскладывают по как можно меньшему числу рюкзаков. Точные решатели задачи упаковки часто работают, снова и снова решая задачи, похожие на задачу о рюкзаке.
Почему приложение допускает только 12 предметов?
Потому что точный ответ перебирает все множества предметов, а 12 предметов дают уже 4 096 множеств. Быстрые правила справились бы с тысячами предметов, но рисунок и сравнение с точным ответом — нет.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать упаковку