问答题
【说明】
假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配 1个不同的任务。
程序中，N个任务从0开始依次编号，N个工人也从。开始依次编号，主要的变量说明如下。
· 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; /*设置的初始值，大于可能的费用*/
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＜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++)
printf("Task%d is assigned to Worker%d\n",i,temp[i]);
}/*main*/
【参考答案】
(1) k==N或k＞=N (2) cose+c[k][i]＜mincost (3) i (4) k+1 (5) wo......
(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)