Алгоритм линейного раскроя (финальный рывок)

[AXS]

В общем решил написать алгоритм линейного раскроя методом полного перебора.

Дано:
N деталей разной длины и неограниченное количество заготовок длиной L
Любая из деталей меньше L
Требуется:
Разместить все детали на заготовки, используя как можно меньше заготовок и при этом остаток от последней заготовки должен быть как можно бОльшим.

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

В аттаче скрин - результат работы алгоритма при 10 деталях разной длины и заготовках длиной 1000. Первые 10 полос - это сами детали (по сути тоже комбинации из одной детали) остальное - их комбинации.
------------------------------------------------------------------------
Теперь то, что я не могу осилить... мозг устал наверное

Надо из этих комбинаций выбрать те которые отвечают условию:

использовать как можно меньше заготовок и при этом остаток от последней заготовки должен быть как можно бОльшим

[AXS]

Мне бы только принцип понять. С какой стороны начать... У кого какие мысли есть - выскажитесь.

[SNUPY]

ИМХО решать надо так... пусть имееться массив загатовок Zag, и деталей Det одинаковой длинны.
1:Возьмем максимальный элемент Det и возьмем наименьшую загатовку в которую он влезет.
2:Уменьшим величину той загатовки которую мы взяли в 1 на величину детали которую взяли в 1.
3: удалим из массива эту деталь
4: если длинна массива >0 то идем к пункту 1, если нет то конец.

Только вот не уверен ^_^

[AXS]

Сообщение от SNUPY

ИМХО решать надо так... пусть имееться массив загатовок Zag, и деталей Det одинаковой длинны.
1:Возьмем максимальный элемент Det и возьмем наименьшую загатовку в которую он влезет.
2:Уменьшим величину той загатовки которую мы взяли в 1 на величину детали которую взяли в 1.
3: удалим из массива эту деталь
4: если длинна массива >0 то идем к пункту 1, если нет то конец.

Только вот не уверен ^_^

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

Кстати одна из коммерческих программ раскроя сделала вот такой крой:

[SNUPY]

А у меня уже варианты наполнения заготовок готовы. Надо только выбрать какие из них составят самый выгодный набор.

Так у вас в задаче два критерия, надо определиться какой значимее ^_^ Или же свести к одному критерию ^_^

[AXS]

Как так какой значимее??? Сначала по первому, потом по второму. То есть минимум заготовок на сколько можно разместить все детали = 6. Но вариантов раскроев на 6 заготовок несколько. Вот теперь по второму критерию.

К примеру моя программа раскроя написанная двумя годами ранее сделала крой тоже на шесть заготовок но остаток от последней заготовки на 50 больше чем сделала программа выше ^ Значит этот крой лучше.

Сравни:

[SNUPY]

а в чем собстсвено проблема если перебрали все возможные варианты?

[AXS]

Сообщение от SNUPY

а в чем собстсвено проблема если перебрали все возможные варианты?

Посмотри внимательно первый пост и скрин к нему...

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

Блин, как ещё объяснить? Кто нибудь объясните ему в чём фишка!..

[SNUPY]

Так а почему же вы не делаете алгоритмом который я тебе предложил? или он не всегда выгоден?

[SNUPY]

Только что надумал... (будем идти перебором)
Пусть M массив состоящий их всех возможных расположений деталей на загатовке. Пусть N массив уже использумемых в раскройке деталей по заготовкам (пока он пуст). Count количестве детай.
1: выберим i-ый элемент массива M такой что его элементы не отмечены N и отметим их в N
2: покуда количество элеменов N не равно Count повторяем 1.
3: обнуляем N....
....
Вот только тоже у самого голова не варит =\ на мысль только одна рекурсия приходит, чтоб его пустить на складывание разных комбинаций =\