阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。【说明】 假设需要将N个任务分配给

Question

阅读以下说明和C程序，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，

但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。

程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：

c[i][j]：将任务i分配给工人j的费用；

task[i]：值为0表示任务i未分配，值为j表示任务i分配给工人j；

worker[k]：值为0表示工人k未分配任务，值为1表示工人k已分配任务；

mincost：最小总费用。

【C程序】

#include＜stdio.h＞

#define N 8 /*N表示任务数和工人数*/

int c[N][N]；

unsigned int mincost=65535； /*设置min的初始值，大于可能的总费用*/

int task[N]，temp[N]，workerIN]；

void Plan(int k，unsigned Int cost)

{ int i；

if ((1)&&cost＜mincost){

mincost=cost；

for (i=0；i＜N；i++) temp[i]：task[i]；

}

else{

for(i=0；i＜N；i++) /*分配任务k*/

if (worker[i]＝0&&(2)){

worker[i]=1； task[k]=(3)；

Plan((4)，cost+c[k][i])；

(5)； task[k]=0；

}/*if*/

}

}/*Plan*/

void main()

{int i，j；

for (i=0；i＜N；i++) { /*设置每个任务由不同工人承担时的费用及全局数组的初值*/

worker[i]=0；task[i]=0； temp[i]=0；

for(j=0；j＜N；j++)

scanf ("%d"，&c[i][j])；

}

Plan (0，0)； /*从任务0开始分配*/

printf("\n最小费用=%d\n"，mincost)；

for(i二0；i＜N；i++)

pnntf("Task%d iB assigned toWorker%d\n",i,temp[i])；

}/*main*/

Answer 1

正确答案：(1)k＞=N或k==N或其等价形式 (2)cost+e[k][i]mincost或其等价形式 (3)i (4)k+1 (5)worker[i]=0或其等价形式
(1)k＞=N，或k==N，或其等价形式 (2)cost+e[k][i]mincost，或其等价形式 (3)i (4)k+1 (5)worker[i]=0，或其等价形式 解析：首先为函数Plan()代码加上行号，以便说明。
  1：void Plan(ihtk,unsigned int cost)
  2：{int i；
  3： if( (1) &&costmincost){
  4：  mincost=cost；
  5：  for(i=0；iN；i++) temp[i]=task[i]；
  6：  }
  7： else{
  8：  for(i=0；iN；i++)  /*分配任务k*/
  9：  if (worker[i]＝0&& (2) ){
  10：  worker[i]=1； task[k]= (3) ；
  11：  Plan( (4) ，cost+c[k][i])；
  12： (5) ； task[k]=0；
  13：  }/*if*/
  14： }/*else*/
  15：}/*Plan*/
  由注释可知，在Plan(k,cost)中，以k表示任务编号、cost表示费用。根据题目中的说明，程序用回溯法计算总费用最小的一种工作分配方案，因此在得到每一个分配方案时需要和先前已经得到的分配方案中的最小费用进行比较。由于需要将N个任务分配给N个工人，以任务为序时，最后一个任务(第N-1个任务)分配之后便得到一种方案，因此第3行代码的空(1)处填入“k＞=N或k==N”。
  显然，在分配任务k时，需要考查所有的工人(第8行代码)，此时若工人i尚未接收任务(worker[i]==0)，并且将任务k分配给工人i不会超出前面某个方案的费用，则可将任务k分配给他(task[k]=i，然后开始分配第k+1个任务。回溯时则需要将分配工人i的任务撤销，以便考查其他的分配方案。