import java.io.*;
public class Batch { //回溯法处理批处理作业调度问题
static int n;//作业数
int[] Order ;//作业顺序
int[] bestOrder;//最优的作业顺序
static int bestf = Integer.MAX_VALUE;;//最优的时间初始化
static int currentf=0;//当前完成用的时间;
static int f1=0;//机器1完成的处理时间;
int[] f2 ;//第i阶段机器2完成的时间;
static Integer[] machine1 ;
static Integer[] machine2 ;
public static void setN(int n) {
Batch.n = n;
}
public static void main(String[] agrs){
Batch batch = new Batch();
BufferedReader br = null;//
File file = new File("D:/Assign04input.txt");
try{
br = new BufferedReader(new FileReader(file));
}catch(FileNotFoundException e){
e.printStackTrace();
return;
}
String line1 = null,line2;
try{
PrintWriter pw = new PrintWriter(new File("D:/Assign04output.txt"));
line1 = br.readLine();
int number = Integer.valueOf(line1);//作业个数
setN(number);
pw.print("作业数为:" + n + "\r\n");
Integer[] machine1 = new Integer[n + 1];
Integer[] machine2 = new Integer[n + 1];
int i = 1;
while((line2 = br.readLine()) != null){
String [] pos = line2.split(" ");
machine1[i] = Integer.parseInt(pos[0]);//机器1处理任务i的时间
machine2[i] = Integer.parseInt(pos[1]);//机器2处理任务i的时间
i ++;
}
pw.print("任务在机器1,2上的处理时间分别是:"+ "\r\n");
for(int k = 1; k <= n;k ++){
pw.print("任务" + k + ": (" + machine1[k] + "," + machine2[k] + ")" + "\r\n");
}
batch.BackTrace(1);
pw.print("作业分配最节省的时间为" + bestf);
pw.print("方案为:");
for (int k=1;k<=n;k++)
{
//pw.print(bestOrder[k] + ",");
}
pw.flush();
pw.close();
}catch(IOException e){
e.printStackTrace();
}
}
public void BackTrace(int i) {
int[] Order = new int[n + 1];
int[] bestOrder = new int[n + 1];
int[] f2 = new int[n + 1];
Integer[] machine1 = new Integer[n + 1];
Integer[] machine2 = new Integer[n + 1];
for(int a = 1;a <= n;a ++){
Order[a] = a;
}
if (i>n) {
for (int i1=1;i1<=n;i1++)
{
bestOrder[i1]=Order[i1];
}
bestf=currentf;
}
else
{
for (int j=i;i<=n;j++)
{
f1+=machine1[Order[j]];
f2[i]=(f2[i-1]>f1?f2[i-1]:f1)+machine2[Order[j]];
currentf+=f2[i];
swap(Order[j],Order[i]);
if (currentf<bestf)
{
BackTrace(i+1);
}
swap(Order[j],Order[i]);
currentf-=f2[i];
f1-=machine1[Order[j]];
}
}
}
private static void swap(int i, int j) {
int temp;
temp = i;
i = j;
j = temp;
return;
}
}