package demo4;

import java.util.Random;

/**
 * 最佳调度问题
 */
public class BestSchedule {

	/**
	 * 任务数
	 */
	int N;
	/**
	 * 机器数
	 */
	int M; 
	/**
	 * 最优值=最优时间
	 */
	int best; 
	/**
	 * 每个任务所需的时间序列
	 */
	int[] t;
	/**
	 * 每台机器所需时间序列
	 */
	int[] len;
	/**
	 * 当前路径=机器编号
	 * x[i]=j：i任务，j机子编号
	 */
	int[] x; 
	/**
	 * 最优调度：其中bestx[i]=m表示把第i项任务分配给第m台机器
	 */
	int[] bestx; 

	public static void main(String[] args) {
		BestSchedule bs = new BestSchedule();
		bs.showTest();
	}

	void showTest() {
		N = 10; // 任务数
		M = 7; // 机器数目
		Random r = new Random();
		// 每个任务的时间
		t = new int[N]; 
		//随机分配每个任务所需要的时间
 		for (int i = 0; i < N; i++) {
			t[i] = r.nextInt(5 * N);
 		}
 		// 记录每台机器所需要的时间
		len = new int[M]; 
		best = Integer.MAX_VALUE;
		// N个任务分配第几台机子
		bestx = new int[N];
		x = new int[N];

		Long startTime = System.nanoTime();
		backtrack(0);
		Long endTime = System.nanoTime();
		System.out.println("总耗时： " + (endTime - startTime) + " ns");

		System.out.print("最优时间：");
		System.out.println(best);
		System.out.print("每个任务所需要时间：");
		for (int i = 0; i < N; i++){
			System.out.print(t[i] + "  ");
		}
		System.out.println();
		System.out.print("最优调度：");
		for (int i = 0; i < N; i++){
			System.out.print(bestx[i] + "  ");
		}
	}

	/**
	 * 回溯搜索
	 * @param dep  任务编号
	 */
	void backtrack(int dep) {
		//打印最优解数据，打印i个任务由那个机子执行效率高
		if (dep == N) {
			//时间
			int tmp = comp();
			//比最优解时间都小
			if (tmp < best) {
				//最优时间
				best = tmp;
				//遍历N个任务
				for (int i = 0; i < N; i++) {
					//第i任务分配给x[i]个机器
					bestx[i] = x[i];
				}
			}
			return;
		}

		//遍历机器
		//
		for (int i = 0; i < M; i++) {
			//第i台机子执行任务所需时间+dep任务所需要的时间
			len[i] += t[dep];
			//机子下标从1开始
			//当前任务dep由i机子执行
			x[dep] = i + 1;
			//i台机子执行完当前dep任务的时间比最优解小，执行下一个任务
			//下一个任务继续循环遍历机子
			//会在最优解时间内执行完任务，那么此任务符合条件
			//问题：导致每台机子执行，都有可能是最优解，每个任务都被所有机子执行
			if (len[i] < best) {
				backtrack(dep + 1);
			}
			//当前机子i执行任务dep，不比最优解小，减去当前dep任务执行的时间
			//继续下一个机子i+1执行dep任务
			len[i] -= t[dep];
		}
	}

	/**
	 * 计算完成任务的时间
	 * @return  机器执行任务时间
	 */
	int comp() {
		//机器完成任务时间
		int tmp = 0;
		//遍历机器
		for (int i = 0; i < M; i++) {
			//当前机器执行任务时间>之前机器执行任务时间
			if (len[i] > tmp) {
				tmp = len[i];
			}
		}
		return tmp;
	}

}