四个工人,四个任务,每个人做不同的任务需要的时间不同,求任务分配的最优方案。(2005年5月29日全国计算机软件资格水平考试——软件设计师的算法题)。
【正确答案】#include "stdafx.h"
#define N 4
int Cost[N][N] = { {2, 12, 5, 32}, // 行号:任务序号,列号:工人序号
{8, 15, 7, 11}, // 每行元素值表示这个任务由不同工人完成所需要的时间
{24, 18, 9, 6},
{21, 1, 8, 28}};
int MinCost=1000;
int Task[N], TempTask[N], Worker[N];
void Assign(int k, int cost)
{
if(k==N)
{
MinCost = cost;
for(int i=0; i<N; i++)
TempTask[i] = Task[i];
}else{
for(int i=0; i<N; i++){
if(Worker[i]==0 && cost+Cost[k][i] < MinCost)
{
Worker[i] = 1; Task[k] = i;
Assign(k+1, cost+Cost[k][i]);
Worker[i] = 0; Task[k] = 0;
}
}
}
}

int main(int argc, char* argv[])
{
Assign(0, 0);
printf("最佳方案总费用=%d/n", MinCost);
for(int i=0; i<N; i++) /* 输出最佳方案 */
printf("/t任务%d由工人%d来做:%d/n", i, TempTask[i], Cost[i][TempTask[i]]);
return getchar();
}
【答案解析】