Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск комбинаций отрезков.

Автор: a678aa 13.4.2016, 01:50

Есть одномерные детали длиной 3,5,7,9,11,13,15. Есть заготовка фиксированной длины 20. Припуски, толщина распила 0. Как получить все возможные комбинации полного заполнения заготовки? То есть интересуют все комбинации типа : 5+15 = 20 3+3+5+9 = 20 7+13 = 20 3+3+3+3+3+5 = 20 Ручками - не реально, деталей намного больше. Подскажите куда копать, интересует сам алгоритм, с какой стороны подойти. Буду благодарен за любые ответы в тему.

Автор: Akina 13.4.2016, 09:10

Цитата(a678aa @  13.4.2016,  02:50 ) интересует сам алгоритм Задача одномерного раскроя. Весьма стандартная и даже не сильно сложная. Некоторые не сильно грамотные товарищи ещё пытаются называть её задачей о рюкзаке. Это неверно, одномерный раскрой - это упрощённая версия рюкзака, когда не учитывается стоимость. Но решения для рюкзака применимы и к раскрою. Добавлено через 2 минуты и 17 секунд Цитата(a678aa @  13.4.2016,  02:50 ) Как получить все возможные комбинации полного заполнения заготовки? А точно нужны ВСЕ варианты? Обычно в реальной задаче целью ставится оптимальный раскрой заготовок для получения заданного набора деталей, а за критерий оптимальности берётся минимизация количества заготовок или (реже) минимизация количества различных раскроев.

Автор: a678aa 13.4.2016, 22:07

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)