Использовано контейнеров
Нижняя граница
Наименьшее возможное

      Веса предметов (кг)

        Подробнее о задаче упаковки в контейнеры

        Задача упаковки в контейнеры

        Коробки в фургоны, файлы на диски, задания на машины: задача упаковки в контейнеры спрашивает, как разместить список предметов в как можно меньшем числе одинаковых контейнеров. Не известно быстрого метода, который всегда находит лучшую упаковку, но простые правила подходят к ней близко. Выберите правило, пройдите его по шагам и сравните с точным ответом. Нажмите на предмет на полке, а затем на контейнер, в который его нужно положить: в зеленых контейнерах для него есть место, а кнопка «Новый контейнер» открывает еще один. Нажмите на предмет в контейнере, чтобы снова вынуть его. Упакуйте все предметы в как можно меньшее число контейнеров; нижняя граница (общий вес, деленный на размер контейнера, с округлением вверх) и наименьшее возможное число показывают, насколько вы близки к цели, а кнопка «Минимум контейнеров» показывает лучшую упаковку. Веса предметов (в килограммах) и размер контейнера можно изменить на панели. Вид «По шагам» показывает, как упаковывают быстрые правила: следующий подходящий, первый подходящий или наилучший подходящий, для предметов в введенном порядке или отсортированных по убыванию, а также точный ответ, найденный динамическим программированием. Нажмите Пуск, чтобы смотреть, как предметы ложатся в контейнеры, или Шаг и Назад, чтобы двигаться по одному шагу, и перетаскивайте ползунок шагов, чтобы перейти в любое место. Когда поле выбрано, клавиши со стрелками делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

        Как это работает

        1. Нажмите на предмет, затем на контейнер, где есть место, чтобы положить его туда, или на «Новый контейнер», чтобы открыть ещё один.
        2. Постарайтесь обойтись как можно меньшим числом контейнеров или нажмите «Минимум контейнеров», чтобы увидеть лучшую упаковку.
        3. Откройте вид «По шагам», выберите правило и нажмите Пуск, чтобы увидеть, как каждый предмет пробует контейнеры.

        Правила

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

        Точный ответ

        Последнее правило — не эвристика: оно находит наименьшее число контейнеров динамическим программированием по множествам предметов. Для каждого множества предметов оно хранит наименьшее число контейнеров, в которые они помещаются, а среди упаковок с таким числом контейнеров — наименьшую загрузку последнего контейнера. Множество растет по одному предмету, который либо добавляется в последний контейнер, либо открывает новый. Для n предметов есть 2ⁿ множеств, поэтому приложение допускает не больше 12 предметов. Нижняя граница — общий размер, деленный на размер контейнера и округленный вверх, — показывает, насколько упаковка близка к лучшей.

        Часто задаваемые вопросы

        Какое правило упаковки лучше всего?

        Из быстрых правил сильнее всего «первый подходящий по убыванию» и «наилучший подходящий по убыванию»: они никогда не используют больше 11/9 от наименьшего числа контейнеров плюс небольшая константа. «Первый подходящий» и «наилучший подходящий» на неотсортированных предметах укладываются в 1,7 от наименьшего числа контейнеров, а «следующий подходящий» — в 2 раза.

        Почему упаковка в контейнеры — трудная задача?

        Решить, помещаются ли предметы всего в два контейнера, — это уже задача о разбиении, а она NP-полна. Поэтому, если только не P = NP, ни один метод не находит наименьшее число контейнеров быстро для любых входных данных, а точные методы в худшем случае требуют экспоненциального времени.

        Что такое нижняя граница?

        Общий размер предметов, деленный на размер контейнера и округленный вверх. Ни одна упаковка не может использовать меньше контейнеров, ведь в них должны поместиться все предметы. Часто лучшая упаковка совпадает с ней, но не всегда: у трех предметов размера 6 и контейнеров по 10 нижняя граница равна 2, а нужно 3 контейнера.

        Это динамическое программирование?

        Точный ответ — да: он строит лучшую упаковку для каждого множества предметов из лучших упаковок меньших множеств. Быстрые правила — жадные методы: они решают один раз и никогда не оглядываются назад.

        Отправляется ли что-нибудь куда-либо?

        Нет. Все вычисляется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

        Готовы попробовать?

        Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

        Перейти в редактор