Java实现调度问题 回溯法

假设有n（n<=20）个任务由k（k<=20）个可并行工作的机器完成。完成任务i需要的时间为ti。 试设计一个算法，对任意给定的整数n和k，以及完成任务i 需要的时间为ti ，i=1~n。计算完成这n个任务的最佳调度，使得完成全部任务的时间最早。

输出格式:将计算出的完成全部任务的最早时间输出到屏幕。

分析：其实这道题就是就是一棵满三叉树，遍历这求得最优结果即可。

import java.util.*;

public class Main {
    static int[] a = {2, 14, 4, 16, 6, 5, 3};//任务时间
    static int n = 7;//任务数量
    static int k = 3;//机器数量
    static int[] x = new int[k];//记录每台机器所累加的时间
    static int bstm = 100000;//初始值无穷大

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        search(0);
        System.out.println(bstm);
    }

    static void search(int t) {
        //抵达叶子结点就是当前递归的终止条件
        if (t >= n) {
            int temp = 0;
            //找到机器中的最长时间（当前路径下时间积累最长的时间为有效结果）
            for (int i = 0; i < x.length; i++) {
                if (x[i] > temp) {
                    temp = x[i];
                }
            }
            //更新最短时间
            if (temp < bstm) {
                bstm = temp;
            }
            return;
        }

        //依靠for循环遍历k叉树宽带(树形结构是k叉树,所以i的上界是k【抽象来看每个结点都有k个子节点】)
        for (int i = 0; i < k; i++) {
            //机器累加上当前任务
            x[i] += a[t];
            //剪枝（如果某台机器的累计时间大于前一条路径的最佳时间，就剪掉）
            if (x[i] < bstm) {
                //依靠递归遍历高度
                search(t + 1);
            }
            //到了叶子结点，开始回溯，试探新的路径
            x[i] -= a[t];
        }
    }
}

tips：想明白是三叉树的话这道题不难，初学者不要被回溯法模板所限制思维。