算法设计例题：批处理作业调度（回溯）
memory limit: 5000KB time limit: 2000MS
accept: 1 submit: 12
Description
给定n个作业的集合 J = { J1，J2，…，Jn }。每一个作业Ji都有两项任务分别在两台机器上完成。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji，其实 i=1，2，…，n，j=1，2。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
Input
输入的第一个为测试样例的个数T（ T < 120 ），接下来有T个测试样例。每个测试样例的第一行是作业个数n（ n <= 7 ），接下来n行，每行两个整数 t1i 和 t2i ，分别表示当前作业在机器1和机器2上的处理时间。（ 0 <= t1i , t2i <= 100 ）
Output
对应每个测试样例输出两行，第一行格式为"Case #: M"，其中'#'表示第几个测试样例（从1开始计），M为最佳作业调度的时间和。第二行为n个以空格分隔的整数，表示最佳作业调度方案中各作业执行顺序的序号。
Sample Input
1
3
2 1
3 1
2 3
Sample Output
Case 1: 18
1 3 2
算法分析：
这里有两台机器，如果将两台机器一起考虑的话，比较难解决。我们可以将只考虑一个问题，因为只要有一台机器处理作业的顺序确定了，另位一台处理作业的顺序也就确定了。将如第一台处理作业的顺序是1，3，2 那么第二台处理作业的顺序也就是1，3，2.在一台作业调度中，作业的顺序邮n! 中，（假设作业顺序是1，2，3）这很明显是一个排列数，当作业2在第一台机上处理时，第2台机器上可能也正在处理作业1，如果作业2处理完后，他有可能处理等待状况，只有第2台机器上的作业1被处理，作业2才能进入第一台机器，（*都懂）.下面的数组开辟可能有出入，大家注意。
#include"iostream"
using namespace std ;
class FlowShop {
public :
int n ; //作业数
int f1;//机器1完成处理时间
int f;//完成时间之和
int bestf;//当前最优值
int m[100][100] ; //各作业所需的处理时间
/*
1 5 6
2 5 7
*/
int x[100];//当前作业调度
int bestx[100];//当前最优作业调度
int f2[100];//机器2完成处理时间
void swap (int x [100] , int i , int j )
{
int t = x[i];
x[i] = x [j ] ;
x[j] = t ;
}
void initilization()
{
f1 = 0 ;
f = 0 ;
bestf = 1000000 ;
int i =0 ;
while(i <= 99 )
{
x[i] = i ;
i++;
///一定要做这一步。
f2[i] = 0 ;
bestx[i] = 0 ;
}
}
void backtrack(int i )
{
if(i>n)
{
for(int j = 1 ; j <= n ; j++ )
bestx[j]=x[j];
bestf = f ;
// cout<< "++++"<<f<<endl;
}
else{
for(int j = i ; j <= n ; j++ )
{
//f1处理机在完成第j作业的时间 = 第一j之前作业和第j作业所需的时间
f1+=m[ x[j] ][ 1 ] ;
//f2
//如果算法没对f2[]初始化将会出错，因为i=1是，f2[i-1] = f2[0]，f2[0]在没初始化时可能会出错
f2[i] = ( ( f2[i-1] > f1 ) ? f2[i-1]:f1 ) + m [ x [j] ] [ 2 ];
//f2[j] = ( ( f2[i-1] > f1 ) ? f2[i-1]:f1 ) + m [ x [j] ] [ 2 ];
//完成时间之和*/
f+=f2[i];
if(f<bestf){
swap (x,i,j);
backtrack(i+1);
swap(x,i,j);
}
f1 -= m[ x[ j ]] [1] ;
f -= f2 [ i ] ;
}
}
}
};
int main(){
int T ;
FlowShop fs ;
cin>>T;
int j =1 ;
while(T>0)
{
cin>>fs.n;
int i = 1 ;
while( i <= fs.n )
{
cin>>fs.m[i][1];
cin>>fs.m[i][2];
// cout<<fs.m[i][1]<<" "<<fs.m[i][2]<<endl;
i++;
}
fs.initilization();
fs.backtrack(1);
i = 1 ;
cout<<"Case "<<j<<": "<<fs.bestf<<endl;
while(i <= fs.n )
{
cout<<fs.bestx[i]<<" " ;
i++;
}
cout<<endl;
j++;
T--;
}
return 0 ;
}