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

                               {

                         case 20:

                   {

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

                         {  b[i]=c[i-(i/3)];

                       b[i+1]=c[num-((i/3)+1)];

                         b[i+2]=c[i-(i/3)+1];

                         i=i+2;}

                               b[18]=c[12];

                               b[19]=c[13];

                     break;}

                     case 50:

                         {

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

                         { b[i]=c[i-(i/3)];

                          b[i+1]=c[num-((i/3)+1)];

                         b[i+2]=c[i-(i/3)+1];

                        i=i+2;}

                               b[48]=c[32];

                               b[49]=c[33];

                     break;}

                     case 100:

                         {

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

                         {  b[i]=c[i-(i/3)];

                       b[i+1]=c[num-((i/3)+1)];

                         b[i+2]=c[i-(i/3)+1];

                        i=i+2;}

                         b[99]=c[66];

                         break;}

                               }

                         upakovka(b);

                         break;}

                         }

                this->Invalidate();

                   textBox1->Text=v.ToString();

                   } 

                   void quick1(kusok* a, int N)

                   {    

                   int i = 0, j = N; // поставить указатели на исходные места

                         kusok temp, p;

       p = a[N>>1]; // центральный элемент

                         // процедура разделения

                         do {      while ( a[i].l < p.l ) i++;

                   while ( a[j].l > p.l ) j--;

                               if (i <= j)

                               {

       temp = a[i]; a[i] = a[j]; a[j] = temp;

                                     i++; j--;

                               }

                         } while (i<=j);

//рекурсивные  вызовы,если есть,что сортировать

                   if ( j > 0 ) quick1(a, j);

                   if ( N > i ) quick1(a+i, N-i);

                   }

 void upakovka(kusok* m)//функция упаковки

                   {

                         while(!glist.empty())

                               glist.clear();//очистка глобального списка

mqueue std_set;//стандартная очередь

                         std_set.len=con;

                         glist.push_back(std_set);

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

                         {

                         if((glist.back().len)>=0)

                               {

                                     glist.back().Q.push(m[j]);

                                     glist.back().len-=m[j].l;

                               }

                               else

                               { 

                                     glist.push_back(std_set);

                                     glist.back().Q.push(m[j]);

                                     glist.back().len-=m[j].l;

                               }

                         }              

                   } 

      private: System::Void Form1_Paint(System::Object^  sender, System::Windows::Forms::PaintEventArgs^  e) {

                         if(list_is_ready)//рисование стержней с заготовками (из списка)

                         {

                   int w=int(ClientSize.Width);

                   int h=int(ClientSize.Height);

 array<Pen^>^ pens=gcnew array<Pen^>(2);//массив карандашей

             pens[0]=gcnew Pen(Color::Green);

             pens[1]=gcnew Pen(Color::Red);

                               Drawing::Font^shrift=gcnew System::Drawing::Font("Courier New",10);//шрифт для строкового вывода

                               Drawing::Brush^pencil1=gcnew System::Drawing::SolidBrush(Color::Black);//крандаш для строкового вывода

                               Drawing::Brush^pencil2=gcnew System::Drawing::SolidBrush(Color::Blue);

 Drawing::Point oxy(240,10);//точка начала для стержня

             int dx=(w-400)/100;

             int dy=(h-20)/(glist.size());

                         int n1=1,n2=1;

                         queue<kusok> bufer;

                         for(list<mqueue>::iterator i=glist.begin();i!=glist.end();i++)

                               {

e->Graphics->DrawString("L"+n1.ToString(), shrift,pencil1,oxy.X-10,oxy.Y);

e->Graphics->DrawLine(pens[0],oxy.X,oxy.Y, oxy.X+100*dx,oxy.Y);

                                     while(!((*i).Q.empty()))

{        bufer.push((*i).Q.front());

                                           oxy.X+=dx*(*i).Q.front().l/10;

e->Graphics->DrawLine(pens[1],oxy.X,oxy.Y-2,oxy.X,oxy.Y+2);

e->Graphics->DrawString("x"+(*i).Q.front() .x.ToString(),shrift,pencil2,oxy.X,oxy.Y+2);

                                           (*i).Q.pop();

}

                                     while(!bufer.empty())

{       (*i).Q.push(bufer.front());

bufer.pop();

                                     }

                                     oxy.X=240;

                                     oxy.Y+=dy;

                                     n1++;

                               }

                               oxy.X=20;

                               oxy.Y=60;

                               int k=1;

                               n1=(int)ceil((double)(h-60)/15.);

                               n2=(int)ceil((double)num/((double)n1));

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

                               {

for(int j=0;(j<n1)&&(k<=num);j++)

                                     {

e->Graphics->DrawString("x"+b[k-1].x.To String()+"="+b[k-1].l , shrift,pencil1,oxy.X-10,oxy.Y);

                                           oxy.Y+=15;

                                           k++;

                                     }

                                     oxy.Y=60;

                                     oxy.X+=75;

                               }

                         }

                   } 

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

                   {

                         this->Invalidate();

                   } 
 
 

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

                   {

                         Close();

                   }

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

                   {

                         Form_d^ SecondForm;

                         SecondForm=gcnew Form_d;

                         SecondForm->Show();

                   }