Алгоритм подбора оптимальных деталей по длине

Пользователь

Сообщений: 531 Регистрация: 14.08.2017

31.01.2019 13:45:11

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

Ограничения:
1. Макрос в первую очередь должен выбирать такой набор деталей что бы их число было наименьшим (это условие в приоритете)
2. Макрос должен выбирать как можно меньшие по длине детали.

Во вложении прилагаю пример с правильными и не правильными результатами.

Не могу придумать алгоритм, по которому обрабатывать данную логику.

Прикрепленные файлы

Пример.xlsx (8.92 КБ)

MCH

Пользователь

Сообщений: 3906 Регистрация: 22.12.2012

31.01.2019 14:05:33

Вопросы:
1. приоритета относительно наименьшего кол-во отрезов нет?
2. в реальности сколько различных элементов?
3. их количество не ограничено?
4. указанные размеры конструкции и элементов реалистичные?
5. что делать с обрезками, они выбрасываются?

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

Изменено: MCH - 31.01.2019 14:06:13

DopplerEffect Пользователь Сообщений: 531 Регистрация: 14.08.2017	#3 31.01.2019 14:11:40 MCH, 1. Приоритетов по отрезам нет 2. В реальности элементов будет около 3-4 3. Размеры реалистичны 4. Обрезки выбрасываются Спасибо за наводку по задаче, сейчас буду смотреть.