Подскажите, пожалуйста, быстрый ( программно) алгоритм для решения
след. задачи:
есть отрез материала длиной L и есть n заготовoк
длиной li . Все числа целые. Для каждого целого k = { 0, 1, 2 … L } надо выбрать несколько  вариантов ( если они есть) раскроя отреза, чтобы
L -∑ li *x i =k где x i - количество заготовок длины li.. Нужно выбирать такие варианты, чтобы было
Как можно больше заготовок одной длины .
На x i наложены ограничения
x i <= b i , b i целые положительные числа

Число заготовок может быть до 20, длина отреза  до  200 00, заготовки длиной от 50 до 500,

Мне надо написать программу, с которой пользователь будет работать в интерактивном режиме, т.е. он вводит длину отреза , длины заготовок и их количество ,
далее нажимает на кнопку и ему на экран выдаются (желательно без видимой задержки ) варианты для выбора раскроя : варианты (когда остаток =к , к от 0, 1, 2 L). Пользователь сам (учитывая др. факторы )
выбирает вариант раскроя. Вообще раскраивается много отрезов и
окончательный вариант для каждого отреза должен выбрать человек, а ему надо предложить выбор. Я видела работающую программу ( похоже на Клиппере, исходника нет,, написанная 15 лет назад) варианты предлагаются мгновенно с остатками от - 0 до L .  Впечатление, что работет цикл по к, для каждого к идет расчет, но очень быстро.
Конечно предлагаются не все варианты, а только те, где меньше разброса по заготовкам ( если это возможно), т.е. надо в один отрез положить как можно больше заготовок
одного вида. 
  Например,  для L=32  заготовки длиной 17, 5, 3, 2   b1=b2=b3=b4=20
 варианты
 17   5    3       2     остаток
-------------------------------
  1    3     -         -       0
  -     6     -        1       0
  -     -     10      1       0
  -     -       -      1 6     0
  1     -     5      -         0

  1    2     -        2       1
  -     5     2        -       1
  -     -      9        2      1
  1    -       -        7      1
  1     -     4        1      1
 т. д.

Можно так делать.

Составляется функция
исходные данные: 
1) длина без отреза - Line
2) длина и колличество 1-й заготовки - l1 и x1
выходные данные:
1) длина остатка - В
2) максимальное колличество заготовок которые можно вырезать - N


Дальше составляется программа, использующая эту функцию

Цикл по отрезу от 0 до L с шагом 1
в нём цикл по всем заготовкам, обращающийся к функции
если получилось B=0 вывод ответа.
если успешно отрезаны все заготовки - тоже вывод и конец 

Это сообщение отредактировал(а) nworm - 9.3.2010, 19:22

Поскольку Вы желаете (судя по тому, что написано) получить ВСЕ варианты раскроя, да ещё в порядке сортировки по остатку - имеется типичная [censored] задача с полным перебором вариантов. И я лично не вижу ровным счётом никаких оснований к тому, чтобы заниматься оптимизацией.

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

В общем - поиск по форуму или Гугль в помощь. Искать фразу "метод ветвей и границ".

Можете тогда просто запрограммировать мой вариант.

Твой вариант и есть частный случай метода ветвей и границ. Кстати, не самый оптимальный.

  Если я правильно поняла Ваш алгоритм, то  ( рассматриваем вариант остаток после раскроя нулевой) надо сначала   макс положить первую заготовку, в оставшийся отрез макс вторую и т. д.  Если в конце остаток нулевой, то это решение, а если  нет,  то надо как-то перебирать варианты.
 Вот реальный пример.   Отрез длиной 5859, заготовки длиной  324, 314, 314, 159,229,104,72  ( здесь две заготовки случайно одной длины , но это разные их нельзя объединять), 
 ограничения по количеству  соответственно  4,9,7,3,2,2,2   . 
  попытки перебора вешают комп, а "старая" программа мгновенно выдала результаты

    4, 9,3,1,2,1,2
    4, 5,7,1,2,1,2
    4, 9,2,3,2,1,0

Это при том, что надо перебрать 5*10*8*4*3*3*3=43200 вариантов? Боюсь, что у Вас программа написана... ммм... с ошибками.

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

Значит, так криво запрограммировано. На VB6 все 8 вариантов находятся за  30 мс.

Добавлено через 8 минут и 53 секунды
На 1С 7.7 процедура генерит массив решений (точное попадание в 5859) за 150 мс.

У Вас полный перебор за 150мс?

Конечно... я же не в БД пишу результаты, а в таблицу в памяти.

Это  фрагмент моего кода
 Подскажите, как сделать лучше


   //===========================
  Процедура ФФ (Сум,н) 
 ц= мин(Цел(Сум/А.ПолучитьЗначение(н)),В.Получитьзначение(н) );    
 
    Для р1=0 по ц  Цикл 
       р=ц-р1;
    Реш.УстановитьЗначение(н,р); 
 
    сум1=Сум-А.ПолучитьЗначение(н)*р;   

    Если Сум1=0 Тогда
     Т.НоваяСтрока(); 
       Для е=1 по н Цикл  
           Т.УстановитьЗначение(Т.НомерСтроки,е,Реш.ПолучитьЗначение(е));
       КонецЦикла;
       Т.УстановитьЗначение(Т.НомерСтроки,"Ост",Сум1);    
    Возврат;
 КонецЕсли;    
    Если н=МаксВым Тогда  
        
           Т.НоваяСтрока(); 
       Для е=1 по МаксВым Цикл  
         
          Т.УстановитьЗначение(Т.НомерСтроки,е,Реш.ПолучитьЗначение(е));
       КонецЦикла;
       Т.УстановитьЗначение(Т.НомерСтроки,"Ост",Сум1);
    
    Иначе    
         ФФ(Сум1,н+1);
    КонецЕсли;    
      
   КонецЦикла;
КонецПроцедуры
 
//==================
Процедура Расчет()            //  перебор всех вариантов у которых сумма меньше Сум     рекурсмя
А=СоздатьОбъект("СписокЗначений");    
В=СоздатьОбъект("СписокЗначений");  
 Сум=5859;
 МаксВым=7;
  А.ИзстрокиСРазделителями("324,314,314,229,159,104,72");  

 В.ИзстрокиСРазделителями("4,9,7,2,3,2,2");     
// В.ИзстрокиСРазделителями("10,10,10,10,10,10,10");      
    
 Реш=СоздатьОбъект("СписокЗначений");        
    
 Т=СоздатьОбъект("ТаблицаЗначений");

Для р=1 по МаксВым цикл
 Т.НоваяКолонка();    
 Реш.ДобавитьЗначение(0);  
Конеццикла;    
    Т.НоваяКолонка("Ост"); 
    Час=0; Ми=0; Сек=0;  
 ТекущееВремя(Час,ми,сек);
 Сообщить(Час*10000+ми*100+сек);
    ФФ(Сум,1);
    Час=0; Ми=0; Сек=0;  
 ТекущееВремя(Час,ми,сек);
 Сообщить(Час*10000+ми*100+сек);
      Т.ВыбратьСтроку();
      Т.Сортировать("Ост");    
      Т.ВыбратьСтроку();
 Сообщить(Т.КоличествоСтрок());     
КонецПроцедуры;    
//

Добавлено через 7 минут и 9 секунд
 А как Вы в 1С  пишите в таблицу в памяти, как в одномерный массив
   Т[к] =... ?

 А как долго ваша программа делает расчет при ограничениях для всех заготовок <=10