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