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