试题详情

试题四
阅读以下说明和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*/