Оптимальный распил палок

Д.в.
Нужен алгоритм для решения следующей задачи или если он есть, то как называется?
Есть доски длинной 2000 мм. Есть список с досками от 300 мм до 1000 мм. Мне нужно написать программу (не важно на каком языке, мне главное алгоритм), которая считает сколько надо досок, чтобы напилить палки из списка с минимальным остатком, что бы сложить все остатки в одну сумму и получилось как можно меньше. ну и соответственно чтобы знать сколько палок надо распилить на какие размеры. Например 10 досок пилим на три палки - 600, 500 и 300, 4 доски пилим на 800 и 900, и т.д.
Что можете предложить? Всю голову сломал. Есть алгоритм "Упаковки рюкзака", но там учитывается "цена" и "Вес", а мне как бы надо просто "вес". заранее спасибо тому кто что то подскажет)

Добавлено через 16 минут
Как думаете? Если взять палку 2000, и методом перебора (благо список не очень большой) подставлять все комбинации с размерами из списка, выбрать оптимальную комбинацию, из списка вычесть палки которые в этой комбинации и прибавить к нужному количеству досок +1 . И так делать до тех пор, пока в списке с палками не останется ничего???
Это будет оптимальный вариант?

0

Сообщение от ЕвгенийАндреич Есть алгоритм "Упаковки рюкзака", но там учитывается "цена" и "Вес", а мне как бы надо просто "вес"

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

1

Лучше брутофорса ничто не решит. Другое дело хватит ли мощности =).

0

Сообщение от Fulcrum_013 Только рюкзаков получается много а не один. палки сортируются по убыванию остатки по возрастанию. Ну и дальше впихивается что куда впихнется. Т.е. наибольшая палка сравнивается с досками начиная с наименьшего остатка, когда найдена остаток оставшийся после ее обрезки вставляется в массив остатков с сохранением упорядоченности. По сути получается выбор минимального остатка куда влезет очередная палка. "т.е. первый подходящий с упорядочиванием" Основной из пользуемых в промышленности методов в силу своей простоты и достаточно высокой эффективности.

Это для вычисления необходимого количества досок. А как то можно сделать , чтобы получить "карту раскроя" - т.е. на какие размеры сколько пилить досок?

0

ЕвгенийАндреич, Ну вот именно карту раскроя так и определяют. При этом для ускорения вместо массива палок можно использовать кучу. Именно поэтому динамическую память и называют еще кучей - для ее "раскроя" тот же алгоритм оптимизации применяется. При этом на практике есть еще такое понятие как нижний предел размера остатка пригодный для дальнейшего использования. С учетом этого факта даже полный перебор если и дает выигрыш то редко и очень незначительный.

0

Вот тут было похожее обсуждение:

Задача на минимизацию остатков

0

Представьте цех 100 000 тон дерева в год и немного неоптимальный раскрой...

Лучше результата чем от брутофорс не существует с природе, его результат это эталон для всех других решений. Другое дело, что не всегда есть вычислительная мощность для него. Поэтому придумывают всякие уловки\усложнения\альтернативы.

Сообщение от ЕвгенийАндреич и методом перебора (благо список не очень большой)

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

0

Сообщение от Excalibur921 Лучше результата чем от брутофорс не существует с природе, его результат это эталон для всех других решений. Другое дело, что не всегда есть вычислительная мощность для него. Поэтому придумывают всякие уловки\усложнения\альтернативы.

Был у нас на городской олимпиаде в 90-х эта задача под названием "задача о нескольких рюкзаках" присутсвовала. Пройтить все тесты смогли только эти два метода - полный перебор рекурсией ака "брут" и "первый подходящий с упорядочиванием". Потому как НИИ Искуственного Интеллекта которое оную олимпиаду организовывало запарилось искать набор данных на которых брут превзошел бы. Хотя такие наборы данных действительно существуют.

0

Кстати, вопрос - это теоретическая задача или практическая?

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

1

Fulcrum_013, спасибо. Работает. Написал программу по твоему алгоритму в VBA Excel, кроит один в один как Базис Мебельщик раскрой. Т.к. у меня все ведется в экселе не хотелось привлекать стороннею программу для раскроя, а так хоп хоп и все работает четко

0

ЕвгенийАндреич, Для эксперимента не пробовали сверять с брутофорсом?
Критерии оценки:
1)размер остатков
2)кол-во строк кода.
3) разбор матана\кода метода

0

Excalibur921, не пробовал, не когда. Я и так проэкт на долго затормозил. Когда закончу, буду его совершенствовать ,вот и попробую

0

Сообщение от ЕвгенийАндреич кроит один в один как Базис Мебельщик раскрой

Реально это одна из первых лабораторок по курсу САПР в универе. Вернее ее половина. Вторая половина то же самое для 2D случая с прямоугольными листами и заготовками. Так что весь раскрой деланный "на скорую руку" работает именно так.

0

Сообщение от ЕвгенийАндреич Как думаете? Если взять палку 2000, и методом перебора (благо список не очень большой) подставлять все комбинации с размерами из списка, выбрать оптимальную комбинацию, из списка вычесть палки которые в этой комбинации и прибавить к нужному количеству досок +1 . И так делать до тех пор, пока в списке с палками не останется ничего??? Это будет оптимальный вариант?

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

PS:
ЕвгенийАндреич, Можете привести пример Ваших исходных данных (реальных)
У меня есть кое-какой опыт по линейному раскрою

0