欢迎来到天天文库
浏览记录
ID:60802223
大小:1.82 MB
页数:17页
时间:2020-12-19
《工作分配问题ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、回溯法之工作分配问题计科二班IMP设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。试设计一个算法,为每一个人都分配1件不同的工作,并使总费用达到最小。问题描述n个工作分配给n个人,并且每个人的工作不同。因此,该问题的解空间是一个排列树。相应的排列树由work[1:n]给出。问题分析在递归算法Backtrack中,当i>n时,算法搜索至叶节点,得到新的排列方案。if当前总费用cc>minc,更新minc。return回i-1层;问题分析当i<=n时,判断cc2、。否则,剪去子树。问题分析给定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、再回溯到第13、个工人重新分配: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");i4、n>>n;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++)in>>c[i][j];}}voidBacktrack(inti){if(i>n){//已得到一个可行解if(cc5、[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!
2、。否则,剪去子树。问题分析给定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、个工人重新分配: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");i
4、n>>n;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++)in>>c[i][j];}}voidBacktrack(inti){if(i>n){//已得到一个可行解if(cc5、[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!
5、[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!
此文档下载收益归作者所有