Задачка по раскрою максимального количества коробок на листе?
Есть задачка нужно сделать раскрой на листе заданого размера, также задается размер желаемых коробок (высота, ширина, глубина), нужно сделать такой раскрой который выдаст максимальное количество коробок.
Подскажите в какую сторону копать.
P.S. Для упрощения, размеры сторон коробки должны быть такими что бы они не накладывались друг на друга. Т.е. на выходе вырезанный картон будет складываться в коробку, но держаться сам по себе он не будет
Lynn «Кофеман», Это уже сверху навешивается, когда имея набор шаблонов и их цены, надо выбрать, что же вырезать, чтобы побольше прибыли получить. Тут же более геометрическая задача - распихать в прямоугольнике как можно болше разверток одинаковых коробок.
Wataru, именно поэтому википедики и пишут не "задача о ранце", а "сводится к задаче о ранце". Задача раскроя - это частный случай задачи о ранце, при условии равенства всех весовых коэффициентов.
Akina, ну блин, задача раскроя, как и задача о ранце - целочисленное линейное программирование. Сформулируйте хоть одно целочисленное линейное уравнение тут.
То, что слово "раскрой" встречается и в вопросе и в названии задачи, не значит, что это та самая задача.
Выглядит, словно вы нагуглили и выдали первую попавшеюся ссылку даже не читая ее.
Wataru, товарищ вообще-то русским по белому пишет - ему надо на двумерный лист положить максимальное количество двумерных же деталей. Ни количеством он не ограничен, ни приоритетом - просто уложить максимальное количество, и всё. Даже ограничения по ориентации детали на листе - и того нету. Чистой воды двумерный раскрой, от ранца даже запаха нет.
А Вы тут какую-то прибыль приплели - откуда Вы её вычитали-то? нету в вопросе этого слова, нету.
Akina, Ранец как раз и взялся из ссылки. И прибыль - оттуда же. И я как раз и говорил, что к этому вопросу это все не применимо.
"на двумерный лист положить максимальное количество двумерных же деталей", вообще говоря - это задача упаковки, а не раскроя. Ну вот так у математиков получилось, что слово "раскрой" занято вот той задачей по ссылке, которая к вопросу отношения не имеет.
Тут нет никакого готового алгоритма. Это геометрическая задача раскроя. Надо порисовать и придумать какой-то паттерн. Рассмотреть несколько случаев и выбрать наилучший в зависимости от ваших размеров.
Есть идеи как можно это сделать?
Учитывая что размеры могут быть произвольными
На сколько я понимаю должен быть какой-то алгоритмический подход.
Я же не могу для каждого размера просчитывать вручную
Вам надо придумать еще парочку, для каждого варианта найти формулу, сколько шаблонов влезет по горизонтали и вертикали в зависимости от размеров листа (W, H) и трех размеров коробки (a, b, c)
Шаблон со сдвигом по диаганали, наверно, не самый эффективный, но это вам на подумать пример.
Например, для верхнего левого варианта влезает x=floor(W/(2a+2b) по горизонтали и y=floor((H-b)/(b+c)). Значит, всего в лист влезет x*y раскроев.
Еще возможны шаблоны, где используется не один вид развертки коробки, а несколько. Потом, еще могут быть всякие хитрые развертки, когда размеры коробки частично совпадают (например, 2 числа одинаковые, а третье больше или меньше). В этом случае могут быть возможны еще варианты расположений коробок. Еще отдельный случай - кубы. Когда у коробок все размеры одинаковые, ими можно замостить плоскость.
Потом вам надо в программе перебрать 6 перестановок всех длин коробки, 2 перестановки размеров листа, подставить во все формулы для разных паттернов и выбрать максимум.
Если коробок влезает мало, то возможно сделать полный перебор, который пытается впихнуть одну из возможных разверток на лист, касаясь уже поставленных там разверток и краев коробки (перебираете все возможные точки касания потом смотрите чтобы нигде ни с чем ничто не пересекалось). Но это может сможет расположить три вместо двух разверток. Если их хотя бы десяток влезает простым шаблоном, то полный перебор будет работать вечность и максимум впихнут 2-3 лишние коробки.
Если совсем лень вручную раскладывать то можно Монте-Карло)) Раскладывать псевдо случайным образом с проверкой на пересечение, то есть встык. Поскольку выкройки очевидно лучше ориентировать по осевым, а не под углом то перебор существенно сократится. Потом обстреливать случайными координатами. Где меньше всего попадёт в молоко тот раскрой и победил))
Средний
