Относительно прямой способ может быть таким: начать с одного стека и дальше перебирать комбинации коробок, чтобы получить второй стек примерно той же высоты, потом – третий стек и т. д. Если не получается подобрать достаточно стеков, надо взять в качестве исходного стек другой высоты – и снова пристраивать к нему следующие. И так до тех пор, пока не найдется высота, которой будет соответствовать такое количество стеков, чтобы они могли покрыть всю площадь палеты. Но перепробовать придется очень много высот, и расчет, как следствие, будет крайне медленным.
Я задумал попробовать другой метод, предполагающий кардинально иное решение.
Что, если сразу найти как можно более многочисленную группу из стеков одной высоты? Для этого можно, например, сосчитать высоты всех стеков от одной до четырех коробок в нашей выборке. Т. е. нужно проверить высоты комбинаций всех коробок со следующими порядковыми номерами:
1, 2, 3, 4;
1, 2, 3, 5;
1, 3, 4, 5;
2, 3, 4, 5
и т. д.
Допустим, у нас в выборке 50 коробок. Тогда последними комбинациями из четырех коробок будут
46, 48, 49, 50;
46, 47, 48, 50;
46, 47, 48, 49;
47, 48, 49, 50.
Кроме того, нужно проверить высоты комбинаций из трех, двух и одной коробки:
от 1, 2, 3 до 48, 49, 50;
от 1, 2 до 49, 50
и от 1 до 50.
Чем больше коробок в выборке, тем стремительнее растет количество этих комбинаций. Для выборки из 50 коробок получаем 230 300 комбинаций, для выборки из 60 коробок – 487 635, для 70 – 916 895, почти миллион. Но высóты всех этих комбинаций, сколько бы их ни было, можно сосчитать очень быстро, за малую долю секунды.
Я решил попробовать так: пересчитать высоты всех комбинаций и построить гистограмму, отображающую, сколько из них попадает в узкий (скажем, 10 мм) интервал высот. Затем взять несколько локальных максимумов этой гистограммы, для каждого из них выбрать стеки, принадлежащие к этому диапазону высот, и попробовать создать из них плоский слой, покрывающий все основание палеты.
Задача все равно оставалась намного сложнее, чем простое составление гистограммы высот. Во-первых, не все комбинации из двух, трех или четырех коробок сложатся в хороший стек. Так, если поставить длинную и узкую коробку в пару с квадратной – в таком стеке будет много пустого места, и нижняя или верхняя поверхность этого стека будет покрывать только часть площади его основания. Или, например, вариант «песочных часов»: две одинаковых широких и плоских коробки, а между ними – высокая с ощутимо меньшей площадью основания. Такой стек будет неустойчивым, и, кроме того, будет продавливаться середина нижней коробки.
В целом стеки из всевозможных комбинаций упаковок нужно отфильтровать по объемной эффективности (процент пустого места от всего объема, занимаемого стеком, – произведения его горизонтальной площади на высоту), по критерию «песочных часов» – чтобы площадь самой маленькой коробки была не намного меньше площади самой большой, – и так, чтобы площади верхней и нижней поверхности стека занимали достаточную долю от площади основания. Лучшие стеки – те, где все коробки примерно одинаковой длины и ширины. После такой фильтрации остается еще достаточно много стеков, из которых можно выбирать. Скажем, в выборке из 70 коробок из первоначальных 916 895 вариантов может остаться порядка 100 000 вполне приемлемых. Максимальные значения гистограмм в таком случае могут содержать более 1000 стеков.
Но это не значит, что любые из них можно отбирать для построения слоя. Для этого каждый стек должен содержать уникальную, неповторяющуюся комбинацию коробок.
Скажем, у нас имеются стеки примерно равной высоты, содержащие следующие комбинации номеров коробок:
1, 12, 19, 34;
8, 11, 19, 41;
1, 22, 32;
12, 15, 41.
Если мы выбираем первый стек для построения слоя, ни один другой для него больше не подходит: коробка 19, присутствующая во втором стеке, уже использована в первом, как и коробка 1 из третьего стека, и коробка 12 – из четвертого. Если же мы начнем со второго стека, мы должны исключить первый и четвертый, тогда как третий не имеет общих коробок со вторым. В этом случае два стека (второй и третий) можно добавить в коллекцию стеков для плоского слоя.
В первоначальном варианте алгоритма я опробовал примерно такой порядок действий. Сначала выбираем один из интервалов высот, куда попадает максимальное число приемлемых стеков. Сортируем стеки в каждом таком интервале по качеству, определяемому как комбинация объемной эффективности, «песочных часов» и еще нескольких подобных критериев. Начинаем отбор с первого стека. В следующих стеках, если какая-то коробка из комбинации, составляющей его, использована в уже отобранных стеках, данный стек пропускается. Если все коробки новые – стек добавляется к коллекции. Таким образом мы доходим до конца списка стеков в этом интервале высот или прекращаем поиск, когда набралось достаточное число стеков, чтобы сделать слой, – возможно, с некоторым избытком, например, чтобы общая площадь проекций стеков в коллекции на 20 % превышала площадь основания палеты. В результате такой процедуры может получиться, например, коллекция стеков с порядковыми номерами в отсортированной последовательности: 1, 3, 8, 17, 31, 50, 78 и т. д. Чем ближе к концу последовательности, тем больше разница между соседними отобранными номерами: все больше коробок уже использовано и все меньше вероятность того, что в следующем стеке окажутся только новые коробки.