问答题
阅读下列说明和C代码，回答下面问题。
[说明]
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a i 和b i 。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤如下。
(1)确定候选解上界为最短的单台处理机处理所有作业的完成时间m：
[说明]
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a i 和b i 。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤如下。
(1)确定候选解上界为最短的单台处理机处理所有作业的完成时间m：
问答题
根据以上说明和C代码，填充C代码中的空白处。
【正确答案】
【答案解析】p[X][y][0]=1
p[X][y][k]=p[x-a[k-1]][y][k-1]
y-b[k-1]＞=0
p[x][y][n]==1或p[X][y][n]或p[x][y][n]!=0
(x＞=y)?x:y 本题是一个求最优解的问题。
第1空所处的位置为schedule()函数的for循环中，从题目的描述和程序不难看出该三重循环的作用是给三维数组p赋初值，而根据题目描述可知数组k=0时，其对应的数组元素值都为1(因为这个时候没有作业，那么肯定可以在A用时不超过x且在B用时不超过y时间内处理完成)，因此第1空应该填p[x][y][0]=l。
第2空在函数schedule()中的第2个三重for循环中，而且是在if结构下，只有if条件的结果为真时，才执行第2空的程序，从题目和程序也不难看出，这个三重for循环的作用就是要实现题目算法描述中的第2步，即求出p数组中各元素的值。那么当x-a[k-1]＞=0为真时，即说明前k个作业可以在A用时不超过x内处理完成，那么根据题目意思，应该p(x，y，k)=p(x-a k ，y，k-1)，因此第2空的答案应该是p[x][y][k]=p[x-a[k-1]][y][k-1]。
第3空if判定的条件表达式，根据条件为真后面执行的语句可以判定出，这里的条件是要判定是否前k个作业可以在B用时不超过y内处理完成，因此第3空的答案是y-b[k-1]＞=0，其实本题与第2空可以参照完成。
第4空在函数write()中，是双重循环下if判定的条件，从题目注释来看，该函数是要确定最优解并输出的，那么结合该函数我们不难知道，确定最优解就是用这个双重循环来实现的。从前面的程序我们知道，所有的解的情况保存在数组p当中，那么现在就是要找出哪个是最优解，其中max是用来存放当前最优解的，而临时变量temp要与max的值做一个比较，将较小的(当前最优)存放在max中，因此求最优解其实就是将所有解做一个比较，然后取出最优解。综上所述，再结合程序，我们不难知道第4空的答案是p[x][y]pn]==1或者类似的表达式，p[x][y][n]=1表示当前情况下有一个解，那么这个解是x还是y呢?这还需要接着判定x与y的值谁更小，将更小的赋值给临时变量temp，因此第5空答案为(x＞=y)?x:y。
p[X][y][k]=p[x-a[k-1]][y][k-1]
y-b[k-1]＞=0
p[x][y][n]==1或p[X][y][n]或p[x][y][n]!=0
(x＞=y)?x:y 本题是一个求最优解的问题。
第1空所处的位置为schedule()函数的for循环中，从题目的描述和程序不难看出该三重循环的作用是给三维数组p赋初值，而根据题目描述可知数组k=0时，其对应的数组元素值都为1(因为这个时候没有作业，那么肯定可以在A用时不超过x且在B用时不超过y时间内处理完成)，因此第1空应该填p[x][y][0]=l。
第2空在函数schedule()中的第2个三重for循环中，而且是在if结构下，只有if条件的结果为真时，才执行第2空的程序，从题目和程序也不难看出，这个三重for循环的作用就是要实现题目算法描述中的第2步，即求出p数组中各元素的值。那么当x-a[k-1]＞=0为真时，即说明前k个作业可以在A用时不超过x内处理完成，那么根据题目意思，应该p(x，y，k)=p(x-a k ，y，k-1)，因此第2空的答案应该是p[x][y][k]=p[x-a[k-1]][y][k-1]。
第3空if判定的条件表达式，根据条件为真后面执行的语句可以判定出，这里的条件是要判定是否前k个作业可以在B用时不超过y内处理完成，因此第3空的答案是y-b[k-1]＞=0，其实本题与第2空可以参照完成。
第4空在函数write()中，是双重循环下if判定的条件，从题目注释来看，该函数是要确定最优解并输出的，那么结合该函数我们不难知道，确定最优解就是用这个双重循环来实现的。从前面的程序我们知道，所有的解的情况保存在数组p当中，那么现在就是要找出哪个是最优解，其中max是用来存放当前最优解的，而临时变量temp要与max的值做一个比较，将较小的(当前最优)存放在max中，因此求最优解其实就是将所有解做一个比较，然后取出最优解。综上所述，再结合程序，我们不难知道第4空的答案是p[x][y]pn]==1或者类似的表达式，p[x][y][n]=1表示当前情况下有一个解，那么这个解是x还是y呢?这还需要接着判定x与y的值谁更小，将更小的赋值给临时变量temp，因此第5空答案为(x＞=y)?x:y。
问答题
根据以上C代码，算法的时间复杂度为______(用O符号表示)。
【正确答案】
【答案解析】O(m
2
n)
本题主要考查时间复杂度，相对于第1题来说，要简单很多。从给出的程序来看，最高的循环是三重循环，因此其时间复杂度为O(m
2
n)或者O(n
3
)。
问答题
考虑6个作业的实例，各个作业在两台处理机上的处理时间如表所示。该实例的最优解为______，最优解的值(即最短处理时间)为______。最优解用(x
1
，x
2
，x
3
，x
4
，x
5
，x
6
)表示，其中若第i个作业在A上处理，则x
i
=1，否则x
i
=2。如(1，1，1，1，2，2)表示作业1、2、3和4在A上处理，作业5和6在B上处理。
|
各个作业在两台处理机上的处理时间
|
||||||
| 作业1 | 作业2 | 作业3 | 作业4 | 作业5 | 作业6 | |
| 处理机A | 2 | 5 | 7 | 10 | 5 | 2 |
| 处理机B | 3 | 8 | 4 | 11 | 3 | 4 |
【正确答案】
【答案解析】(1，1，2，2，1，1)
15 在本题给出的实例中，如果我们用题目描述的方式来求解，其过程也是相当复杂的，因为在题目描述的情况下，数组p的长度为(33+1)*(33+1)*(6+1)，由于我们不是计算机，要计算出该数组中的各元素，肯定也不容易。在这种情况下，因为题目给出的作用只有6个，因此可以采用观察法，不难发现，本题最优解的值为15，最优解为(1，1，2，2，1，1)或者(2，1，2，1，2，2)。
15 在本题给出的实例中，如果我们用题目描述的方式来求解，其过程也是相当复杂的，因为在题目描述的情况下，数组p的长度为(33+1)*(33+1)*(6+1)，由于我们不是计算机，要计算出该数组中的各元素，肯定也不容易。在这种情况下，因为题目给出的作用只有6个，因此可以采用观察法，不难发现，本题最优解的值为15，最优解为(1，1，2，2，1，1)或者(2，1，2，1，2，2)。