Простые однопроходные эвристики для решения одномерной задачи покрытия

      private: System::Void button5_Click(System::Object^  sender, System::EventArgs^  e)

                   {

m=new kusok[num];

v=0;

for(int i=0;i<num;i++)

{      m[i].l=v1+rand()%(v2-v1);//случайное заполнение массива заготовок

m[i].x=i+1;//назначение номера заготовке

        v=(v+m[i].l);

                         }

v=v/1000;

b=new kusok[num];

                 for(int i=0;i<num;i++)

                         { b[i].l=m[i].l;

 b[i].x=i+1; 

                         }

                   }

      };

} 

Описание  параметров программы 
 

Пользователь  выбирает количество деталей(m), диапазон длины деталей и эвристику.

Далее генерируются длины деталей в заданном диапазоне.

Рассчитывается  идеальное покрытие

И производится покрытие форм:

Вычислительный  эксперимент 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Анализ  результатов 

В результате мы видим, чем больше количество деталей (m) выбирает пользователь, тем больше разница между идеальным покрытием и тем, что мы имеем, при любой эвристике.

Для классов c большими размерами покрывающих деталей лучше работают эвристики NF и NFD(с сортировкой элементов по принципма LLS, LSS и SLS). Для остальных классов все эвристики равноценны между собой.