Подсказки с алгоритмом упаковки одинаковых прямоугольников в прямоугольниках с гильотинным ограничением?

Мне поручили создать для знакомого программу, которая рассчитывает, как лучше всего разместить книжные страницы на большом листе бумаги для печати и вырезания.

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

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


algorithm packing
person Thanos Maravel    schedule 19.04.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

Случай 1: упакуйте меньшие прямоугольники так, чтобы их длины были параллельны ширине большего прямоугольника, пока не станет не хватать места. Затем попробуйте наоборот (длина большего прямоугольника параллельна длине меньшего) на доступном пространстве.

Случай 2: упакуйте меньшие прямоугольники так, чтобы их длины были параллельны длине большего прямоугольника, пока не станет не хватать места. Затем попробуйте наоборот (длина большего прямоугольника параллельна ширине меньшего) на доступном пространстве.

Возьмите максимум случая 1 и случая 2, чтобы получить максимальное количество меньших прямоугольников, которые можно упаковать в больший. Код реализации Python 3 можно найти здесь: http://geekzonelive.blogspot.in/2016/06/packing-similar-small-rectangles-into.html

person Haris Ali Khan    schedule 11.06.2016
comment
Привет, я тоже в такой же ситуации, но ссылка на код не работает, не могли бы вы предоставить обновленную? Большое спасибо - person Pablo Rodriguez; 16.10.2020

arrow_upward
0
arrow_downward

Это классическая проблема упаковки, сводимая к проблема с рюкзаком. Популярная версия называется Проблема резки материала, поскольку она включает в себя промышленные процессы резки бумаги (как и ваша проблема). . Проблема NP-сложная, и для ее решения используются методы целочисленного программирования (комбинаторная оптимизация). Существуют более общие проблемы с упаковкой упаковочного изделия. Думаю, вы найдете больше прямоугольников здесь.

person beedot    schedule 19.04.2014