批处理作业调度问题

/*
	Name: 批处理作业调度问题
	Copyright: free
	Author: 巧若拙 
	Date: 17-07-17 14:12
	Description: 
		问题描述：
　　给定n个作业，集合J=（J1，J2，J3）。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理，然后再由机器2处理。
作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。
则所有作业在机器2上完成处理时间和f=F2i，称为该作业调度的完成时间和。
简单描述：
　　对于给定的n个作业，指定最佳作业调度方案，使其完成时间和达到最小。
*/
#include<iostream>
#include<cmath>

using namespace std;

const int N = 3; //作业的个数
int map[N+1][2] = {{0,0},{2,1},{3,1},{2,3}};//记录作业时间安排表 
int P[N+1], bestP[N+1];//分别存储当前作业调度和最优调度
int f2[N+1];//机器2依次完成每项作业的时间 
int f1, f, bestf; //分别存储机器1完成作业时间，机器2完成作业总用时和当前最优时间值 

void Backtrace(int t); //递归回溯 

int main() 
{
	f1 = f = 0;
	bestf = 32758;
	for (int i=0; i<=N; i++)
	{
		f2[i] = 0;
		P[i] = i;
	}
    Backtrace(1);
    
    cout << bestf << endl;
    for (int i=1; i<=N; i++)
	{
		cout << bestP[i] << " ";
	}
	cout << endl;
   
  // system("pause");
   return 0;
}

void Backtrace(int t) //递归回溯，t表示第t号作业 
{
    if(t > N)
    {
        for(int i=1; i<=N; i++)
        {
            bestP[i] = P[i];
        }
        bestf = f;
    }
    else
    {
        for(int i=t; i<=N; i++)
        {
			f1 += map[P[i]][0];
			f2[t] = (f1 > f2[t-1] ? f1 : f2[t-1]) + map[P[i]][1];
			f += f2[t];
			if (f < bestf)
			{
				swap(P[t], P[i]); 
				Backtrace(t+1);
				swap(P[t], P[i]);
			}
			f1 -= map[P[i]][0];
			f -= f2[t];
        }
    }
}