Алгоритм оптимального раскроя линейных материалов

#cpp #алгоритм #php #delphi #javascript

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

Ответы

Ответ 1

Эта задача в англоязычной литературе носит название Cutting stock problem и является
одной из разновидностей задачи о рюкзаке, когда рюкзаков несколько.

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


Ответ 2

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

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