1922_算法设计例题：批处理作业调度（回溯）

给定n个作业的集合 J = { J₁，J₂，…，J_n }。每一个作业J_i都有两项任务分别在两台机器上完成。每个作业必须先由机器1处理，然后由机器2处理。作业J_i需要机器j 的处理时间为t_ji，其实 i=1, 2, …, n，j=1, 2。对于一个确定的作业调度，设F_ji是 作业i 在 机器j 上完成处理的时间。所有作业在机器2上完成处理的时间之和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

输入的第一个为测试样例的个数T，接下来有T个测试样例。

每个测试样例的第一行是作业个数n（ n ≤ 7 ），接下来n行，每行两个整数 t_1i 和 t_2i ，分别表示当前作业在机器1和机器2上的处理时间。（ 0 ≤ t_1i , t_2i ≤ 100 ）

对应每个测试样例输出两行，第一行格式为"Case #: M"，其中'#'表示第几个测试样例（从1开始计），M为最佳作业调度的时间和。第二行为n个以空格分隔的整数，表示最佳作业调度方案中各作业执行顺序的序号。

1
3
2 1
3 1
2 3

Case 1: 18
1 3 2