工作分配问题

回溯法之工作分配问题计科二班IMP设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。问题描述n个工作分配给n个人，并且每个人的工作不同。因此，该问题的解空间是一个排列树。相应的排列树由work[1:n]给出。问题分析在递归算法Backtrack中，当in时，算法搜索至叶节点，得到新的排列方案。if当前总费用ccminc，更新minc。return回i-1层；问题分析当i=n时，判断ccminc？即判断work[1:i]的费用是都优于当前最优值。若满足，则以深度优先方式递归搜索子树。否则，剪去子树。问题分析给定3件工作，i号工人完成j号工作的费用如下：1023234345问题示例1、利用回溯法思想，首先分配的是：10：c[1][1]3:c[2][2]5:c[3][3]cc=18问题示例2、此时，所有工人分配结束，回溯到第2个工人重新分配：10：c[1][1]4:c[2][3]4:c[3][2]cc=18问题示例3、第2个工人已经回溯到n，再回溯到第1个工人重新分配：2：c[1][3]2:c[2][1]5:c[3][3]cc=9问题示例4、回溯到第2个工人重新分配：2：c[1][2]4:c[2][3]3:c[3][1]cc=9问题示例5、再回溯到第1个工人重新分配：3：c[1][3]2:c[2][1]4:c[3][2]cc=9问题示例6、回溯到第2个工人重新分配：3：c[1][3]3:c[2][2]3:c[3][1]cc=9问题示例•classWork{//工作类•public:•Work(){}•voidBacktrack(inti){}•voidOutput(){}•public:•intn,i,j;•int**c;•int*work;•intcc,minc;•voidswap(int&a,int&b){}•};ClassWorkWork()Work(){cc=0;minc=10000;ifstreamin(input.txt);inn;work=newint[n+1];for(i=1;i=n;i++)work[i]=i;•c=newint*[n+1];for(i=1;i=n;i++)c[i]=newint[n+1];for(i=1;i=n;i++){for(intj=1;j=n;j++)inc[i][j];}}•voidBacktrack(inti){•if(in){//已得到一个可行解•if(ccminc)//更新最小费用•minc=cc;•return;•}•for(intj=i;j=n;j++)•{•if(ccminc){//搜索子树•swap(work[i],work[j]);•cc+=c[i][work[i]];•Backtrack(i+1);•cc-=c[i][work[i]];•swap(work[j],work[i]);•}•}•}Backtrack(inti)•intmain(){•Workwk;•wk.Backtrack(1);•wk.Output();•return0;•}MainThankYou!