CPP

C++回溯法实例2

设有A、B、C、D、E五人从事J1、J2、J3、J4、J5五项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使效益最高。
  J1  J2  J3  J4  J5
A 13  11  10   4   7
B 13  10  10   8   5
C  5   9   7   7   4
D 15  12  10  11   5
E 10  11   8   8   4

#include <iostream.h>
int a[5],b[5],cheap,xiaoyi;
int e[5][5]={{13,11,10,4,7},{13,10,10,8,5},{5,9,7,7,4},{15,12, 10,11,5},{10,11,8,8,4}};
void gongzuo(int i,int j);

void jianzhi()
{
      if(xiaoyi<cheap)
      {
            xiaoyi=cheap;
            for(int l=0;l<5;l++)
                b[l]=a[l];
      }
      for(int i=4;i>-1;i--)//回溯
            if(a<4)
            {
                cheap-=e[a];
                gongzuo(i,a+1);
            }
            else cheap-=e[a];
}

void gongzuo(int i,int j)
{
      int flage=0;
      if(i>0)
      {//不能同列
            for(int k=0;k<i;k++)
                if(a[k]==j) flage=1;
      }
      if(flage==0)
      {
            cheap+=e[j];
            a=j;
            if(i<4)
            {
                gongzuo(i+1,0);
                cheap-=e[j];
            }
            else jianzhi();
      }
      else
      {
            if(j<4) gongzuo(i,j+1);
            else if(i>0)
            {//寻找可以符合条件的节点
                for(int l=i-1;l>-1;l--)
                      if(a[l]<4)
                      {
                          cheap-=e[l][a[l]];
                          gongzuo(l,a[l]+1);
                      }
                      else cheap-=e[l][a[l]];
            }
      }
}

void main()
{
      xiaoyi=0;
      cout<<"最高效益安排为:";
      gongzuo(0,0);
      cout<<xiaoyi<<endl;
      for(int i=0;i<5;i++)
            cout<<"第"<<char(i+65)<<"个人做第"<<b+1<<"个任务"<<endl;
}