Вообщем есть палки профиля разной длины (от 1.5 до 5.3 м) из них нужно делать отрезки ещё меньшего размера исходя из потребности покупателя.

Посоветуйте алгоритм, которым генерить всевозможные комбинации раскроя, а я из этого массива выберут схемы раскроя с минимальными обрезками.

Сейчас сделал так (и вроде даже работает):
1. Сначала сортируется таблица остатков по убыванию и таблица потребностей по возрастанию.
2. Затем начинается перебор этих двух таблиц вложенными циклами.
Т.е. на первом витке мы пихаем самую длинную заготовку (заказанную покупателем) в самый короткий обрезков (из имеющихся на складе).
Внутри этих двух циклов есть ещё цикл по количеству, ведь одна и та же заготовка может несколько раз уместиться в одном обрезке.
3. Сортирурую таблицу значений с полученными схемами раскроя и беру с минимальными отходами.
4. Уменьшаю соответствующие цифры в таблице остатков и потребностей. Удаляются строки с нулевыми значениями.
5. Иду на новый виток рекурсии в (1), пока не закончится таблица остатков, или таблица потребностей.

задача о ранце, не?

ЗЫ ты куда пропал-то? я уже начал переживать

к примеру есть на складе 1000 палок по 5.4 метра. Пять палок по 3.7 метра, две палки по 1.5 метра и 15 палок по 2.1 метра.

Заказчик просит продать ему 2 отрезка профиля по 1.7 м и 3 по 1.2 метра.
Из каких палок их напилить чтобы было минимум отходов?

(2) всё уже придумано до нас

wiki:Задача_раскроя
wiki:Задача_о_ранце

(4) ты алгоритм давай

ОО, помню писал раскрой (листовой правда, это сложнее) на генетических алгоритмах. Прикольная штука. 1С-ке будет тяжело, много вычислений )

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

http://www.cutting.com.ua/

(0) Не точно заданы условия задачи.
Как палки не пили, длина остатков не изменится.

Например
одним способом остались отходы: 2м + 1м
другим способом остались отходы: 2.5м + 0.5м
как видно, количество отходов не меняется. Но какой из них лучше не понятно.

сделал так:

Процедура ПоискОптимальныхСхемРаскроев(ТаблицаРезультат,ТаблицаНехваткиПоНоменклатуре,ВыборкаХарактеристикаНоменклатуры,ВыбНоменклатура)

ТаблицаРезультатОптимСхем = новый ТаблицаЗначений;
ТаблицаРезультатОптимСхем.Колонки.Добавить("ХарактеристикаНоменклатурыРаскраиваемая",Новый ОписаниеТипов("СправочникСсылка.ХарактеристикиНоменклатуры"));
ТаблицаРезультатОптимСхем.Колонки.Добавить("КоэффициентХарактеристики",Новый ОписаниеТипов("Число"));
ТаблицаРезультатОптимСхем.Колонки.Добавить("КоличествоОстатков",Новый ОписаниеТипов("Число"));
ТаблицаРезультатОптимСхем.Колонки.Добавить("ОбрезокПалки",Новый ОписаниеТипов("Число"));
ТаблицаРезультатОптимСхем.Колонки.Добавить("МассивПолучаемыхРазмеров");

МассивПолучаемыхРазмеров = новый ТаблицаЗначений;
МассивПолучаемыхРазмеров.Колонки.Добавить("ХарактеристикаНоменклатуры",Новый ОписаниеТипов("СправочникСсылка.ХарактеристикиНоменклатуры"));
МассивПолучаемыхРазмеров.Колонки.Добавить("КоэффициентХарактеристики",Новый ОписаниеТипов("Число"));

ВыборкаХарактеристикаНоменклатуры.Сортировать("КоэффициентХарактеристики Возвр");
ТаблицаНехваткиПоНоменклатуре.Сортировать("КоэффициентХарактеристики Убыв");

Для каждого СтрокаОстатков Из ВыборкаХарактеристикаНоменклатуры Цикл
//Прогоняем каждый типоразмер на остатках через рекурсию
Если СтрокаОстатков.ОстКоличествоПалок > 0 Тогда
МассивПолучаемыхРазмеров.Очистить();
РекурсивноПолучитьВсеСхемыРаскроя(ТаблицаРезультатОптимСхем,СтрокаОстатков.ХарактеристикаНоменклатуры,СтрокаОстатков.КоэффициентХарактеристики,СтрокаОстатков.ОстКоличествоПалок,Число(СтрокаОстатков.КоэффициентХарактеристики),ТаблицаНехваткиПоНоменклатуре,МассивПолучаемыхРазмеров);
КонецЕсли;
КонецЦикла;


//Теперь пилим согласно полученным схемам
ТаблицаРезультатОптимСхем.Сортировать("обрезокПалки возвр, КоличествоОстатков убыв");
...

КонецПроцедуры // ()

Процедура РекурсивноПолучитьВсеСхемыРаскроя(ТаблицаРезультатОптимСхем,ХарактеристикаНоменклатурыРаскраиваемая,КоэффициентХарактеристики,ОстКоличествоПалок,ОбрезокПалки,ТаблицаНехваткиПоНоменклатуре,МассивПолучаемыхРазмеров)

Если ТаблицаНехваткиПоНоменклатуре.Количество()>0 Тогда
СтрокаНулевая = ТаблицаНехваткиПоНоменклатуре[0];
Для КолЗаготовокВПалке = 1 по СтрокаНулевая.ТребКоличествоПалок Цикл
Если ОбрезокПалки >= СтрокаНулевая.КоэффициентХарактеристики Тогда

ОбрезокПалки = ОбрезокПалки - СтрокаНулевая.КоэффициентХарактеристики;
НоваяСтрокаВСхемеРаскроя = МассивПолучаемыхРазмеров.Добавить();
НоваяСтрокаВСхемеРаскроя.ХарактеристикаНоменклатуры = СтрокаНулевая.ХарактеристикаНоменклатуры;
НоваяСтрокаВСхемеРаскроя.КоэффициентХарактеристики = СтрокаНулевая.КоэффициентХарактеристики;

Если ОбрезокПалки = 0 Тогда
//Удача - безотходное производство
НоваяСтрокаВариантовРаскроя = ТаблицаРезультатОптимСхем.Добавить();
НоваяСтрокаВариантовРаскроя.ХарактеристикаНоменклатурыРаскраиваемая = ХарактеристикаНоменклатурыРаскраиваемая;
НоваяСтрокаВариантовРаскроя.ОбрезокПалки = ОбрезокПалки;
НоваяСтрокаВариантовРаскроя.КоэффициентХарактеристики = КоэффициентХарактеристики;
НоваяСтрокаВариантовРаскроя.КоличествоОстатков = ОстКоличествоПалок;
НоваяСтрокаВариантовРаскроя.МассивПолучаемыхРазмеров = МассивПолучаемыхРазмеров;
Прервать;

Иначе
Если ОбрезокПалки = 1.5 Тогда
//ходовой размер, надо эту схему тоже запомнить
НоваяСтрокаВариантовРаскроя = ТаблицаРезультатОптимСхем.Добавить();
НоваяСтрокаВариантовРаскроя.ХарактеристикаНоменклатурыРаскраиваемая = ХарактеристикаНоменклатурыРаскраиваемая;
НоваяСтрокаВариантовРаскроя.ОбрезокПалки = ОбрезокПалки;
НоваяСтрокаВариантовРаскроя.КоэффициентХарактеристики = КоэффициентХарактеристики;
НоваяСтрокаВариантовРаскроя.КоличествоОстатков = ОстКоличествоПалок;
НоваяСтрокаВариантовРаскроя.МассивПолучаемыхРазмеров = МассивПолучаемыхРазмеров.Скопировать();
КонецЕсли;

МассивСтрокДляКопирования = новый Массив;
Для Индекс = 2 ПО ТаблицаНехваткиПоНоменклатуре.Количество() Цикл
МассивСтрокДляКопирования.Добавить(ТаблицаНехваткиПоНоменклатуре[Индекс-1]);
КонецЦикла;
//обязательно передавать копию таблиц, а не сами таблицы
РекурсивноПолучитьВсеСхемыРаскроя(ТаблицаРезультатОптимСхем,ХарактеристикаНоменклатурыРаскраиваемая,КоэффициентХарактеристики,ОстКоличествоПалок,Число(ОбрезокПалки),ТаблицаНехваткиПоНоменклатуре.Скопировать(МассивСтрокДляКопирования),МассивПолучаемыхРазмеров.Скопировать());
КонецЕсли;
Иначе
Прервать;
КонецЕсли;
КонецЦикла;
КонецЕсли;


КонецПроцедуры

(13) 1. отсортируй материал от меньшего к большему, а нужные отрезки от большего к меньшему. Берёшь первый отрезок, подставляешь в первый материал, если не подходит, иди к следующему материалу (или отрезку) и т.д.

(14) эту схему я реализовал в (0), но потом передалал на (12)

(13) Тогда все просто. Перебираешь вообще все возможные варианты, и выбираешь лучший по твоему способу

(15) чтобы получить всё дерево, тебе надо брать одну детальку и пихать во все материалы, это будет первоначальный набор вариантов. Потом для каждого варианта распихиваешь вторую детальку по всем материалам и т.д.

Имхается мне, что нафиг это не нужно

Если не знаешь как перебрать все, то щас пишу

(16) КЭП

(24) Тогда что ты еще хочешь?