Общий смысл: Необходимо изготовить 100 деталей различной длинны. Длинна заготовки 6000 мм. необходимо оптимально разложить детали, что бы получить минимальный отход. Оставшиеся детали оптимально разложить на следующей заготовке и т.д.
Конкретнее: Есть 100 различных значений (могут повторяться). Необходимо найти значения, сумма которых, будет максимально близка к определённому значению. Выписать все значения и удалить их из общего списка. С оставшимися значениями проделать процедуру описанную выше.
На данный момент у меня получается из 20 значений выбрать оптимальный вариант. Но при увеличении количества первоначальных значений, увеличивается время расчёта, почти в геометрической прогрессии, .
Тоже интересует, смотрю за веткой. У меня по аналогии схема распиловки деревянных балок для стропильной системы скатной кровли. Обычными формулами даже мысли нет как делать. Пока понятен только результат:
Доска 1, 6000мм = 3700мм+1200мм+1100мм+ Отход 0мм Доска 2, 6000мм = 3700мм + 2200мм + отход 100мм Доска 3, 6000мм = 2500мм+2500мм + 800мм + отход 200мм и т.д. пока не будут задействованы все размеры
при Этом, если в стране пропала доска 6м (или доску 3м предлагают в 2 раза дешевле) - то нужно быстро сориентироваться сколько нужно доски 3м (и сколько элементов длиннее 3м, чтобы по ним заложить еще доски на сращивание + вытекающие расходы на крепеж, работу и тп
в прикладном плане так: в расчете получилось что достаточно N досок и есть таблица раскроя. Затем доски приезжают на стройку и нумеруются. Рабочий смотрит на таблицу, ищет номер доски и размечает. другой рабочий пилит и складирует по типоразмеру + подписывает. Кровельщик по месту пилит только примыкания от углов
С учётом пропила. В макросе он учитывается "толщина реза". Пилить пилой. Материал швеллер, труба, профильная труба, пруток. Для лазерного станка используем специальную прогу и получаем лист раскроя.
Предполагаю что с помощью массива скорость обработки данных увеличится, но принцип перебора данных в массиве и выдачи его наилучшего результата мне не ясен.
стандартно задача раскроя линейного (арматура, труба, профиль и пр.) материала на детали выглядит так: есть базовая длина заготовка (часто 6 м) есть ширина пропила есть множество деталей с двумя параметрами длина и количество задача: определить минимально необходимое количество заготовок для изготовления заданного ассортимента деталей ------------------- решение делится на 2 части 1. определяются все возможные схемы раскроя (сколько и каких деталей можно сделать из одной заготовки). таких схем может оказаться сотни, тысячи и десятки тысяч (в каждой такой схеме остаток меньше длины самой короткой детали или вообще равен 0) 2. собственно решение: определяется сколько заготовок по какой схеме разрезать чтобы в итоге получить полный набор деталей (а порезанных заготовок минимум)
Решение приложено в первом посте. Но там у меня использовано 20 деталей это около миллиона комбинаций. Время работы макроса 13 сек. При большем количестве (нужно до 100 деталей), это мин. 100891344545564193334812497256 комбинаций.
Поэтому я спрашиваю может есть другой способ перебора? Отличного от моего?
да существует тысячи других способов обьясните что за задачу с сотней деталей вы решаете я напишу вам что получилось у меня и сколько времени заняли расчеты
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
Есть конструкция, сборочно-сварная, которое состоит из множества деталей. Материал деталей одинаковый (предположим швеллер). Но материал может меняться. Это необходимо для подсчёта веса. Размер деталей 1200мм-4шт, 850мм-4шт, 760мм-5шт, 230мм-1шт, 185мм-7шт. Заготовка 6000 мм или 4000 мм (она должно быть изменяемой) Задача: 1-посчитать сколько необходимо выдать материала со склада (мин. кол-во заготовок и общий вес выдаваемого материала) что бы изготовить детали. 2-сообщить сколько останется от каждой заготовки после отрезки деталей (для возможности использовать в дальнейшем). 3-всю информацию вывести на лист, где будет сказано какие детали необходимо отрезать от каждой заготовки, а так же первые 2 пункта.
PS: Есть готовые программные решения которые делают линейный раскрой, есть как бесплатные, так и платные Качество раскроя может быть разным
PPS: Можете приложить свои данные, даже очень сложные, раскрою любой (разумный) набор данных Варианты используемых алгоритмов: жадный алгоритм, решение задачи о рюкзаке (сумма подмножеств), линейное программирование с перебором всех вариантов раскроя Совокупное сочетание данных алгоритмов может дать приемлемый результат по скорости решения и качеству раскроя.
Констатин Л написал: при Этом, если в стране пропала доска 6м (или доску 3м предлагают в 2 раза дешевле) - то нужно быстро сориентироваться сколько нужно доски 3м (и сколько элементов длиннее 3м, чтобы по ним заложить еще доски на сращивание + вытекающие расходы на крепеж, работу и тп
Могу помочь с выбором Приложите реальный набор данных, стыковки углов у меня нет, над этим нужно поработать, а так смогу раскроить даже сложные наборы данных
В #7 пример, а по поводу стыковки - там все просто: перехлест на стыке 800мм, соотв для доски 8500 нужна целая 6м + обрезанная по типу остальных(2500+800=3300). Это могу просто формулами переводить в длины менее длины заготовки с получением кол-ва целых заготовок
МСН, спасибо за готовое решение по ссылке. работает идеально. лучшее чем мог себе представить. Варианты оптимизировать остатки (с учетом возможности использовать перехлест и сращивание) буду искать в июле, обязательно обращусь.