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

[s.Creator]

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

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

А как ТВОЯ программа выбирала лучший раскрой?

[SNUPY]

А как ТВОЯ программа выбирала лучший раскрой?

Помоему он раскраивает по жадному алгоритму ^_^

[AXS]

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

Помоему он раскраивает по жадному алгоритму ^_^

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

PS: Два года назад, кроме как на "жадный" алгоритм я просто не решился на что то серьёзнее

[SNUPY]

И скора я понимаю вы хотите пойти методом перебора?

[AXS]

Не исключаю другие, более разумные варианты.
Но пока ничего подобного на ум не идёт.

[SNUPY]

ночью я надумал следующее....
во рекусрия выбора.. (M массив использованных вариантов из все возможных):

Procedure ChangeOptimal;
var
 i:integer;
begin
  CreateCorrectList(Chg);//создает нормальный список с учетом уже выбранных и записывает в массив N. Сhg массив выбранных
  for i:=0 to length(N)-1 do
  begin 
    Change(N[i]);//продцедура добавлет N[i] в Chg
    if Not AllDetails(Chg) then
    //если не использованы все детали, то опять вызываем
    ChangeOptimal
    else 
    //если использованы все детали, то проверяем на оптимальность по сравнению с предъидущим оптимумом и при необходиости заменем оптимум на этот вариант.
    Optimun;
  end;
end;

[JTG]

Попробуй найти

Л.В. Канторович, В.А. Залгаллер "Рациональный раскрой промышленных материалов." Издательство "НАУКА", Сибирское отделение, Новосибирск, 1971

Там должен быть жутко тормозной алгоритмический метод, который даст на 100% оптимальное решение, чувак Нобелевскую премию за это получил