Задачка по раскрою максимального количества коробок на листе?

Question

[KuzmenkoArtem]

Есть задачка нужно сделать раскрой на листе заданого размера, также задается размер желаемых коробок (высота, ширина, глубина), нужно сделать такой раскрой который выдаст максимальное количество коробок.
Подскажите в какую сторону копать.

P.S. Для упрощения, размеры сторон коробки должны быть такими что бы они не накладывались друг на друга. Т.е. на выходе вырезанный картон будет складываться в коробку, но держаться сам по себе он не будет

Comments

[Lynn «Кофеман»]

https://ru.m.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4...

[Wataru]

Lynn «Кофеман», Это уже сверху навешивается, когда имея набор шаблонов и их цены, надо выбрать, что же вырезать, чтобы побольше прибыли получить. Тут же более геометрическая задача - распихать в прямоугольнике как можно болше разверток одинаковых коробок.

[Akina]

Wataru, именно поэтому википедики и пишут не "задача о ранце", а "сводится к задаче о ранце". Задача раскроя - это частный случай задачи о ранце, при условии равенства всех весовых коэффициентов.

[Wataru]

Akina, ну блин, задача раскроя, как и задача о ранце - целочисленное линейное программирование. Сформулируйте хоть одно целочисленное линейное уравнение тут.

То, что слово "раскрой" встречается и в вопросе и в названии задачи, не значит, что это та самая задача.

Выглядит, словно вы нагуглили и выдали первую попавшеюся ссылку даже не читая ее.

[Akina]

Wataru, товарищ вообще-то русским по белому пишет - ему надо на двумерный лист положить максимальное количество двумерных же деталей. Ни количеством он не ограничен, ни приоритетом - просто уложить максимальное количество, и всё. Даже ограничения по ориентации детали на листе - и того нету. Чистой воды двумерный раскрой, от ранца даже запаха нет.

А Вы тут какую-то прибыль приплели - откуда Вы её вычитали-то? нету в вопросе этого слова, нету.

[Wataru]

Akina, Ранец как раз и взялся из ссылки. И прибыль - оттуда же. И я как раз и говорил, что к этому вопросу это все не применимо.
"на двумерный лист положить максимальное количество двумерных же деталей", вообще говоря - это задача упаковки, а не раскроя. Ну вот так у математиков получилось, что слово "раскрой" занято вот той задачей по ссылке, которая к вопросу отношения не имеет.

Answer 1

[Wataru]

Тут нет никакого готового алгоритма. Это геометрическая задача раскроя. Надо порисовать и придумать какой-то паттерн. Рассмотреть несколько случаев и выбрать наилучший в зависимости от ваших размеров.

Comments

[KuzmenkoArtem]

Есть идеи как можно это сделать?
Учитывая что размеры могут быть произвольными
На сколько я понимаю должен быть какой-то алгоритмический подход.
Я же не могу для каждого размера просчитывать вручную

[Wataru]

KuzmenkoArtem, Вот примеры возможных расположений.



Вам надо придумать еще парочку, для каждого варианта найти формулу, сколько шаблонов влезет по горизонтали и вертикали в зависимости от размеров листа (W, H) и трех размеров коробки (a, b, c)
Шаблон со сдвигом по диаганали, наверно, не самый эффективный, но это вам на подумать пример.

Например, для верхнего левого варианта влезает x=floor(W/(2a+2b) по горизонтали и y=floor((H-b)/(b+c)). Значит, всего в лист влезет x*y раскроев.

Еще возможны шаблоны, где используется не один вид развертки коробки, а несколько. Потом, еще могут быть всякие хитрые развертки, когда размеры коробки частично совпадают (например, 2 числа одинаковые, а третье больше или меньше). В этом случае могут быть возможны еще варианты расположений коробок. Еще отдельный случай - кубы. Когда у коробок все размеры одинаковые, ими можно замостить плоскость.

Потом вам надо в программе перебрать 6 перестановок всех длин коробки, 2 перестановки размеров листа, подставить во все формулы для разных паттернов и выбрать максимум.

Если коробок влезает мало, то возможно сделать полный перебор, который пытается впихнуть одну из возможных разверток на лист, касаясь уже поставленных там разверток и краев коробки (перебираете все возможные точки касания потом смотрите чтобы нигде ни с чем ничто не пересекалось). Но это может сможет расположить три вместо двух разверток. Если их хотя бы десяток влезает простым шаблоном, то полный перебор будет работать вечность и максимум впихнут 2-3 лишние коробки.

[uvelichitel]

Если совсем лень вручную раскладывать то можно Монте-Карло)) Раскладывать псевдо случайным образом с проверкой на пересечение, то есть встык. Поскольку выкройки очевидно лучше ориентировать по осевым, а не под углом то перебор существенно сократится. Потом обстреливать случайными координатами. Где меньше всего попадёт в молоко тот раскрой и победил))

[KuzmenkoArtem]

Wataru, Спасибо! Есть пища для размышлений