workshare.cpp

用数据结构实现基本算法 用C++实现任务分配功能

#include "result.h"
#include<iomanip.h>
//实现问题矩阵的数据类型
typedef struct{
	double elem[MAX_D+1][MAX_D+1];
	int m,n;
	}arrage;
arrage cost;
int job[MAX_D+1];
void BackTracking();
//主程序模块
void main()
{
    //输入问题矩阵
	int i,j,flag=0;
	cout<<endl<<"Input Data:";
	//提示输入开始
	do{
		cout<<endl<<"Input Human Number:(1.."<<MAX_D<<")";        //提示输入人数
		cin>>cost.m;
		cout<<endl<<"Input Job Number:(1.."<<MAX_D<<")&&(<=Human Number)";//提示输入将要
		cin>>cost.n;                                                         //分配的工作数目
		if((cost.m<cost.n)||(cost.m<1)||(cost.m>MAX_D)||(cost.n<1)||(cost.n>MAX_D)){//当参加分配的人数小于可
			cout<<endl<<"Illegal Data. Please Input Again.";      //分配工作数时判为非法
			flag=0;                                               //提示重新输入
			}//if
			else flag=1;
		}while(flag==0);//do..while
	//提示输入第i人干第j项工作的经费消耗
	//经费消耗要大于等于0否则判为非法并提示重新输入
	for(i=1;i<=cost.m;i++){
		cost.elem[i][0]=-1;
		for(j=1;j<=cost.n;j++)
			do{
				cout<<endl<<"cost["<<i<<","<<j<<"]";
				cin>>cost.elem[i][j];
				if (cost.elem[i][j]<0){
					cout<<endl<<"Illegal Data.Please Input Again.";
					flag=0;
					}//if
					else flag=1;
				}while(flag==0);//while
		}//for
	//格式输出问题矩阵
	for(i=1;i<=cost.m;i++){
		cout<<endl;
		for(j=1;j<=cost.n;j++) cout<<setw(8)<<cost.elem[i][j];
		}//for
 cout<<endl;
 //调用处理模块
 BackTracking();
}

//处理模块的实现
void BackTracking()
{
 int j,count;
 double v,totalCost;
 Stack s;
 RList a;
 InitStack(s);
 InitRList(a);
 //初始化job数组
 for(j=0;j<(MAX_D+1);j++) job[j]=FALSE;
 count=0;//定义已分配工作的计数器
 j=0; totalCost=MAXINT; v=0;
 Push(s,j);
 do{
	while((StackLength(s)<cost.m)&&(j<=cost.n)){		//遍历递归树找一条没有冲突的由根到叶子的通路
		if ((cost.elem[StackLength(s)+1][j]!=0)&&(job[j]!=TRUE)){
			Push(s,j);
			if (j!=0) job[j]=TRUE;
			if (j!=0) {v+=cost.elem[StackLength(s)][j];count+=1;}
			j=0;
			}//if
		else j+=1;
		}//while
	//判断是否最优解并将解入解的数组
	if ((StackLength(s)>=cost.m)&&(count==cost.n)){
		SaveResult(s,totalCost,v,a); //存储解向量
		if (totalCost>v) totalCost=v;
		}
	//回溯遍历兄弟
	if (StackLength(s)>0){ //如果栈不空退栈
		Pop(s,j);
		job[j]=FALSE;
		if (j!=0) {v-=cost.elem[StackLength(s)+1][j];count-=1;} //退栈恢复数据
		j+=1;
		}//if
	}while((StackLength(s)>0)||(j<(cost.n+1)));
 OutputResult(a);
 cout<<endl<<"totol cost="<<totalCost<<endl;
}