问答题
【说明】
假设需要将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({{U}} (1) {{/U}} && 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 && {{U}}(2) {{/U}}){
worker[i]=1; task[k]={{U}} (3) {{/U}};
plan({{U}} (4) {{/U}},cost+c[k][i]);
{{U}}(5) {{/U}}; 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) worker[i]=0
[分析]
本题考查回溯法的算法思想。
填充均集中在函数plan中，主函数main只是输入相关数据，调用plan函数，并输出结果。
函数的结构是一个if-else，在else块中调用了函数自身，因此该函数是一个递归函数，if块就是递归出口。在if块中，将cost赋值给mincost，而imncost是用来存储最小总费用的，接着将当前分配方案task保存到temp中，可见if块执行的条件是所有任务分配完成且当前总费用小于mincost。从main函数中调用plan(0，0)的注释：从任务0开始分配，可知，形参k表示当前分配的任务号，cost为当前分配的费用和。任务编号从0开始，故当编号为N时表示任务己分配完。故空(1)应填k==N。
else块中，从工人列表中找一个合适的工人分配任务k，并进行回溯，寻找最优解。函数的目的是寻找总费用最小的分配方案，因此当前分配费用和大于当前最好分配方案总费用的分配方案就不必考虑了。当然只有工人处于空闲状态才能给他分配任务。故空(2)应填cost+c[k][i] ＜mincost。注意c[k][i]表示将任务k分配给工人i的费用。task数组是用来记录任务分配情况的，在此将任务k分配给了工人i，故应将task[k]赋值为i。故空(3)应填i。空(4)处递归调用自身，自然是继续分配下一个任务，即任务k+1，故空(4)应填k+1。至此尚未回溯，空(5)正是用于回溯的，所谓回溯就是将上—个分配的任务换一种方案重新分配以遍历所有的分配方案，也可从紧接着的语句task[k]=0看出，将任务k置为未分配，既然任务k未分配，那么被分配工作的工人i也变为空闲。故空(5)应填worker[i]=0。