[试题]

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

参考答案与解析:

相关试题

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