一、实验内容及要求
1．要求用回溯法原理求解问题；
2．要求手工输入t1[10]及t2[10],t1[i]是任务i在机器1上的执行时间，t2[i]是任务i在机器2上的执行时间；
3．求出最优批处理作业调度总时间及作业安排顺序。
二、实验步骤
1、手工输入任务执行时间数组；
2、输出作业总时间和作业的安排顺序。
package saunfafenxi;
import java.util.Scanner;
public class shiyan5 {
static int worknum=3; //作业总数
static int[] T1 = new int[worknum]; //第i个任务在机器一上面执行的时间
static int[] T2 = new int[worknum]; //第i个任务在机器一上面执行的时间
static int[] jieguo = new int[worknum]; //保存结果的辅助数组
static int[][] mission2 = new int[worknum][2];//第i个任务在机器一上面执行的时间
int bestFinishtime = Integer.MAX_VALUE; //最短时间
int[] schedule = {0,1,2}; //默认的策略顺序。
int[] bestSchedule = new int[worknum]; //最佳顺序
int[] f2 = new int[worknum]; //第二台机器的每个任务的结束时间
int f1,totaltime; //f1当前任务的结束时间，f2的总时间
public void swap(int[] str,int m,int n){
int temp = str[m];
str[m] = str[n];
str[n] = temp;
}
public void BackTrack(int t){ //当搜索到叶子节点后，将这次遍历的策略赋值到最佳策略。
if(t>worknum-1){
bestFinishtime = totaltime;
for(int i=0;i<worknum;i++)
bestSchedule[i] = schedule[i];
return;
}
for(int i=t;i<worknum;i++){ //下面执行的是第t次的任务，全部遍历剩下的可能性。
f1+=mission2[schedule[i]][0];
if(t==0)
f2[t]=f1+mission2[schedule[i]][1];
else
f2[t] = ((f2[t-1]>f1)?f2[t-1]:f1)+mission2[schedule[i]][1];
totaltime += f2[t];
//如果该作业处理完之后，总时间已经超过最优时间，就直接回溯。
if(totaltime<bestFinishtime){
swap(schedule,t,i); //把选择出的原来在i位置上的任务序号调到当前执行的位置t
BackTrack(t+1);
swap(schedule,t,i); //进行回溯，还原，执行该层的下一个任务。
}
f1 -= mission2[schedule[i]][0];
totaltime -= f2[t];
}
}
public static void main(String[] args){
Scanner in_t1 = new Scanner(System.in);
System.out.println("请输入各任务在机器1上的执行时间："); //循环输入T1数组
for(int i=0;i<worknum;i++){
T1[i]=in_t1.nextInt();}
System.out.println("请输入各任务在机器2上的执行时间："); //循环输入T2数组
for(int i=0;i<worknum;i++){
T2[i]=in_t1.nextInt();}
System.out.println("| -----各个作业所需时间如下---- |");
System.out.println("| 作业 | 机器1 | 机器2 |");
for(int i=0;i<worknum;i++){
int s=i+1;
System.out.println("| 作业"+s+" | "+T1[i]+" | "+T2[i]+" |"); //循环输出T1数组
}
for(int i=0;i<worknum;i++){ //各个任务所需时间的二维数组
mission2[i][0]=T1[i];
mission2[i][1]=T2[i];
}
shiyan5 bs = new shiyan5();
bs.BackTrack(0);
System.out.println("
使用回溯得出的作业安排顺序如下:");
for(int i=0;i<worknum;i++){
jieguo[i]=bs.bestSchedule[i]+1;
System.out.print("任务"+jieguo[i]+"
");}
System.out.println("作业完成的总时间是"+bs.bestFinishtime);
}
}
结果截图：
