批处理作业调度-回溯法

class Flowshop
{
    friend Flow(int * *,int,int[]);
private:
    void Backtrack(int i);
    int * * M,
        * x,
        * bestx,
        * f2,
        f1,
        f,
        bestf,
        n;
};
void Flowshop::Backtrack(int i)
{
    if(i>n)
    {
        for(int j=1;j<=n;j++)
            bestx[j] = x[j];
        bestf = f;
    }
    else
    {
        for(int j=i;j<=n;j++)
        {
            f1+=M[x[j]][i];
            f2=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];
            f+=f2[i];
            if(f<bestf)
            {
                Swap(x[i],x[j]);
                Backtrack(i+1);
                Swap(x[i],x[j]);
            }
            f1 -= M[x[j]][1];
            f -= f2[i];
        }
    }
}
int Flow(int * * M,int n,int bestx[])
{
    int ub = INT_AMX;
    Flowshop X;
    X.x = new int [n+1];
    X.f2 = new int [n+1];
    X.M = M;
    X.n = n;
    X.bestf = ub;
    X.bestx = bestx;
    X.f1 = 0;
    X.f = 0;
    for(int i=0;i<=n;i++)
    {
        X.f2[i] = 0;
        X.x[i] i;
    }
    X.Backtrack(1);
    delete [] X x;
    delete [] X f2;
    return X.bestf;
}

#include <iostream>
using namespace std;
#define MAX 200
int* x1;//作业Ji在机器1上的工作时间；
int* x2;//作业Ji在机器2上的工作时间；

int number=0;//作业的数目；

int* xOrder;//作业顺序；
int* bestOrder;//最优的作业顺序；

int bestValue=MAX;//最优的时间；
int xValue=0;//当前完成用的时间；
int f1=0;//机器1完成的处理时间；
int* f2;//第i阶段机器2完成的时间；


void BackTrace(int k)
{
     if (k>number)
     {
          for (int i=1;i<=number;i++)
          {
             bestOrder[i]=xOrder[i];
          }
          bestValue=xValue;
     }
 else
 {
      for (int i=k;i<=number;i++)
      {
           f1+=x1[xOrder[i]];
           f2[k]=(f2[k-1]>f1?f2[k-1]:f1)+x2[xOrder[i]];
           xValue+=f2[k];
           swap(xOrder[i],xOrder[k]);
           if (xValue<bestValue)
           {
                BackTrace(k+1);
           }
           swap(xOrder[i],xOrder[k]);
           xValue-=f2[k];
           f1-=x1[xOrder[i]];
      }
  
 }
}
int main()
{
     cout<<"请输入作业数目：";
     cin>>number;
     x1=new int[number+1];
     x2=new int[number+1];
     xOrder=new int[number+1];
     bestOrder=new int[number+1];
     f2=new int[number+1];

     x1[0]=0;
     x2[0]=0;
     xOrder[0]=0;
     bestOrder[0]=0;
     f2[0]=0;

     cout<<"请输入每个作业在机器1上所用的时间："<<endl;
     for (int i=1;i<=number;i++)
     {
      cout<<"第"<<i<<"个作业=";
      cin>>x1[i];
     }

     cout<<"请输入每个作业在机器2上所用的时间："<<endl;
     for (i=1;i<=number;i++)
     {
      cout<<"第"<<i<<"个作业=";
      cin>>x2[i];
     }

     for (i=1;i<=number;i++)
     {
        xOrder[i]=i;
     }
     BackTrace(1);
     cout<<"最节省的时间为："<<bestValue;
     cout<<endl;
     cout<<"对应的方案为：";
     for (i=1;i<=number;i++)
     {
         cout<<bestOrder[i]<<"  ";
     }
     return 0;
}