Задача гильотинного раскроя

Задача гильотинного раскроя — задача комбинаторной геометрии, близкая к задаче раскроя и задачам упаковки в контейнеры. Вопрос задачи — как получить максимальное число листов прямоугольного размера из листа большего размера, делая только гильотинные разрезы, то есть прямые разрезы от края до края.

Как и задача раскроя, является NP-полной задачей. Существует серия приближённых и точных алгоритмов решения задачи гильотинного раскроя.

Задача гильотинного раскроя важна при производстве листового стекла: листы стекла надрезаются горизонтальными и вертикальными прямыми, а затем разламываются вдоль надреза.

Источник: Википедия

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я