2005年5月29日全国计算机软件资格水平考试——软件设计师的算法题

四个工人，四个任务，每个人做不同的任务需要的时间不同，求任务分配的最优方案。（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(“最佳方案总费用=%dn”, MinCost);

     for(int i=0; i<N; i++)      /* 输出最佳方案 */

         printf(“t任务%d由工人%d来做：%dn”, i, TempTask[i], Cost[i][TempTask[i]]);

}