[简答题] 试题四
阅读以下说明和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
#define N 8 /*N表示任务数和工人数*/
int c[N][N];
unsigned int mincost = 65535; /*设置min的初始值,大于可能的总费用*/
int task[N],temp[N],worker[N];
void plan(int k,unsigned int cost)
{int i;
if (_____(1)_____&& cost < mincost){
mincost = cost;
for (I=0;I}
else {
for ( i = 0 ; iif ( 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;