В общепринятых терминах:
Пусть размеры большой коробки
, а размеры маленькой
. Тогда очевидна система равенств:
Задача заключается в том, чтобы минимизировать свободные коэффициенты
. (или максимизировать
).
Задача сложнее - в некоторых случаях если коробки повертеть в разных направлениях, то можно добиться более оптимальной укладки
Коробочки можно плотно уложить в виде прямоугольного параллелепипеда (назовем это блоком) так, что ШГВ этого блока будут кратны ШГВ коробочек. Блок нужно собрать побольше, но чтобы он мог уместиться в контейнере. Возникает несколько комбинаций помещения блока «максимального размера» в контейнер, если учитывать возможность поворота блока на 90 градусов. Блок нужно задвигать в дальний левый угол контейнера. Спереди, справа и сверху может остаться свободное пространство. Его также можно попытаться заполнить блоками. С учетом порядка заполнения «спереди, справа и сверху» и поворотов блоков возникает некоторое некосмическое количество вариантов…
При большом контейнере и маленьких коробочках это почти оптимально.
Спасибо, по поводу составления блоков - у меня тоже появилась такая идея. Только оптимальной может быть комбинация из некоторого количества различных "блоков", по-разному повернутых.
В общем, судя по всему задача сводится к:
1. Перебору на каждом шаге всех возможных блоков и их "ориентаций" (это несложно)
2. Перебору на каждом шаге всех возможных "нижних левых дальних" углов, в которые можно попытаться вставить каждый из блоков (вот это - какая-то довольно непростая задача, в которой, думаю, вылезет куча различных нюансов, каждый из которых нужно мелочно обсчитать)
3. Выбору оптимального размещения из перебираемых вариантов
Всем большое спасибо за комментарии.
Осталось собраться с силами в свободное от работы время... :)