Тема является продолжением линейного раскроя и задачи о рюкзаке Задачу двумерной упаковки в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP) можно сформулировать так: Имеем набор из N прямоугольников и полуограниченный контейнер-стакан с фиксированной шириной W и бесконечной высотой. Каждый прямоугольник по ширине не превышает W. Задача — уложить прямоугольники в стакан без наложений и пересечений так, чтобы стакан стал как можно менее полон. Подробное описание задачи и варианты жадных алгоритмов есть здесь
Мной реализован совершенно другой алгоритм, основанный на линейном программировании В отличие от условий в статье на habr прямоугольники можно поворачивать на 90 градусов (либо отключать эту возможность)
Суть алгоритма: Укладываем прямоугольники по полосам/уровням При этом генерируем все возможные раскладки прямоугольников в одну полосу, здесь как раз используется алгоритм генерации всех рациональных вариантов разложения из задачи линейного раскроя Составляем линейную модель и решаем ее через целочисленное линейное программирование, где целевая функция будет - минимизация высоты стакана (длины раскраиваемого рулона), при котором укладываются все прямоугольники, не менее заданного количества Для сокращения количества вариантов схем раскроя, а их может быть и несколько сотен тысяч и миллионы (при этом оптимальное решение, как правило, невозможно найти за разумное время), можно задавать ограничение в виде количества различных прямоугольников в одном уровне, также допустимый процент не менее которого будет использоваться схема укладки и другие ограничители Также можно указать допустимо ли вращать прямоугольники или нет. Алгоритм хорошо себя показывает на наборах данных, когда перечень исходных прямоугольников не очень большой но прямоугольники имеют множество повторений.
Применяется гильотинный раскрой, т.е. от края до края, так режется, например, стекло. При этом алгоритм не предназначен для раскроя листового материала, когда заданы размеры листов и нужно раскроить все прямоугольники используя наименьшее количество листов (ДСП или стекло), только для полуограниченной полосы Ширина реза не используется, при резке стекла или пленки ширина реза равна нулю (но если очень нужно использовать ширину реза, то ее можно добавить к размерам прямоугольников).
Примеры получаемых раскроев во вложении Рабочую программу можно скачать здесь: https://disk.yandex.ru/d/-ZbzYEJ2kdPLag Файл cbc.exe должен находится вместе с файлом xls, в одной папке Сложные примеры алгоритм может очень долго считать, нужно указывать ограничения (количество различных элементов в ряду и др.)
Тема является продолжением линейного раскроя и задачи о рюкзаке Задачу двумерной упаковки в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP) можно сформулировать так: Имеем набор из N прямоугольников и полуограниченный контейнер-стакан с фиксированной шириной W и бесконечной высотой. Каждый прямоугольник по ширине не превышает W. Задача — уложить прямоугольники в стакан без наложений и пересечений так, чтобы стакан стал как можно менее полон. Подробное описание задачи и варианты жадных алгоритмов есть здесь
Мной реализован совершенно другой алгоритм, основанный на линейном программировании В отличие от условий в статье на habr прямоугольники можно поворачивать на 90 градусов (либо отключать эту возможность)
Суть алгоритма: Укладываем прямоугольники по полосам/уровням При этом генерируем все возможные раскладки прямоугольников в одну полосу, здесь как раз используется алгоритм генерации всех рациональных вариантов разложения из задачи линейного раскроя Составляем линейную модель и решаем ее через целочисленное линейное программирование, где целевая функция будет - минимизация высоты стакана (длины раскраиваемого рулона), при котором укладываются все прямоугольники, не менее заданного количества Для сокращения количества вариантов схем раскроя, а их может быть и несколько сотен тысяч и миллионы (при этом оптимальное решение, как правило, невозможно найти за разумное время), можно задавать ограничение в виде количества различных прямоугольников в одном уровне, также допустимый процент не менее которого будет использоваться схема укладки и другие ограничители Также можно указать допустимо ли вращать прямоугольники или нет. Алгоритм хорошо себя показывает на наборах данных, когда перечень исходных прямоугольников не очень большой но прямоугольники имеют множество повторений.
Применяется гильотинный раскрой, т.е. от края до края, так режется, например, стекло. При этом алгоритм не предназначен для раскроя листового материала, когда заданы размеры листов и нужно раскроить все прямоугольники используя наименьшее количество листов (ДСП или стекло), только для полуограниченной полосы Ширина реза не используется, при резке стекла или пленки ширина реза равна нулю (но если очень нужно использовать ширину реза, то ее можно добавить к размерам прямоугольников).
Примеры получаемых раскроев во вложении Рабочую программу можно скачать здесь: https://disk.yandex.ru/d/-ZbzYEJ2kdPLag Файл cbc.exe должен находится вместе с файлом xls, в одной папке Сложные примеры алгоритм может очень долго считать, нужно указывать ограничения (количество различных элементов в ряду и др.)MCH
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
