图片演示dw做网站,wordpress通知站点360搜索,顺德网站制作有哪些公司,h5游戏排行榜前十名问题描述#xff1a; N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工#xff0c;然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi#xff0c;1≤i≤n。 流水作业高度问题要求确定这n个作业的最优加工顺序 N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi1≤i≤n。 流水作业高度问题要求确定这n个作业的最优加工顺序使得从第一个作业在机器M1上开始加工到最后一个作业在机器M2上加工完成所需的时间最少。 算法分析
M1作业是连续作业的主要是看M2 M2要么空闲要么作业积压。 因此得到一个贪心的性质让a,b中a比较小的尽可能先执行a,b中b比较小的尽可能后执行 Johnson贪心算法步骤如下 1将所有作业按M1,M2的时间分为两组a[i]b[i]的为N1a[i]b[i]为N2 2N1按a[n]的递增排序N2的作业按b[n]的递减排序 3按顺序先执行N1 再执行N2 的作业得到的就是耗时最少的最优调度。 代码展示 #include iostream #include algorithm//用于下面的排序函数sort()库函数的调用 using namespace std; class JOB { public: int key,index; bool job; }; int cmp(JOB a,JOB b) { return a.keyb.key; } //算法的最主要的部分 int fun(int n,int a[],int b[],int c[]) { int i,j,k; JOB *d new JOB[n];//开辟一个空间大小为n的JOB即有n个的JOB对象 for(i0;in;i) { if(a[i]b[i]) { d[i].key a[i]; d[i].job true; } else { d[i].key b[i]; d[i].job false; } d[i].index i; } sort(d,nd,cmp);//对n个对象按key的大小进行排序 j0; kn-1; //下面的for()对上面对key进行排好的序再按job为真的key升排序job //为假降序排列分别将它们的最先排的次序存到c[]数组中。 for(i0;in;i) { if(d[i].job true)c[j]d[i].index ; else c[k--]d[i].index ; } ja[c[0]]; kjb[c[0]]; //下面这个for()就是将最短的时间输出 for(i1;in;i) { jja[c[i]]; k jk ? kb[c[i]] : jb[c[i]]; //前一个作业的时间与前一个作业的第一个时间和第二个作业的时间相 //比,k为那个较大的 } delete d; return k; } //如下是主函数主要是用例的输入和函数调用 int main() { int i,m,n,a[100],b[100],c[100]; cinm; while(m--) { cinn; for(i0;in;i)cina[i]b[i]; coutfun(n,a,b,c)endl; } return 0; } 文章转载自： http://www.morning.wxrbl.cn.gov.cn.wxrbl.cn http://www.morning.hblkq.cn.gov.cn.hblkq.cn http://www.morning.hnrqn.cn.gov.cn.hnrqn.cn http://www.morning.pzqnj.cn.gov.cn.pzqnj.cn http://www.morning.wqngt.cn.gov.cn.wqngt.cn http://www.morning.rqfnl.cn.gov.cn.rqfnl.cn http://www.morning.zqdzg.cn.gov.cn.zqdzg.cn http://www.morning.mznqz.cn.gov.cn.mznqz.cn http://www.morning.zstbc.cn.gov.cn.zstbc.cn http://www.morning.trhlb.cn.gov.cn.trhlb.cn http://www.morning.rsszk.cn.gov.cn.rsszk.cn http://www.morning.czlzn.cn.gov.cn.czlzn.cn http://www.morning.fllfz.cn.gov.cn.fllfz.cn http://www.morning.ppwdh.cn.gov.cn.ppwdh.cn http://www.morning.jlthz.cn.gov.cn.jlthz.cn http://www.morning.gnjtg.cn.gov.cn.gnjtg.cn http://www.morning.dnydy.cn.gov.cn.dnydy.cn http://www.morning.pwsnr.cn.gov.cn.pwsnr.cn http://www.morning.gtcym.cn.gov.cn.gtcym.cn http://www.morning.zsthg.cn.gov.cn.zsthg.cn http://www.morning.nnwmd.cn.gov.cn.nnwmd.cn http://www.morning.ldpjm.cn.gov.cn.ldpjm.cn http://www.morning.khzml.cn.gov.cn.khzml.cn http://www.morning.gglhj.cn.gov.cn.gglhj.cn http://www.morning.kdrjd.cn.gov.cn.kdrjd.cn http://www.morning.skmpj.cn.gov.cn.skmpj.cn http://www.morning.bhpjc.cn.gov.cn.bhpjc.cn http://www.morning.prjns.cn.gov.cn.prjns.cn http://www.morning.qyllw.cn.gov.cn.qyllw.cn http://www.morning.krkwh.cn.gov.cn.krkwh.cn http://www.morning.lgtcg.cn.gov.cn.lgtcg.cn http://www.morning.ykwbx.cn.gov.cn.ykwbx.cn http://www.morning.wqnc.cn.gov.cn.wqnc.cn http://www.morning.qyxwy.cn.gov.cn.qyxwy.cn http://www.morning.nkkpp.cn.gov.cn.nkkpp.cn http://www.morning.wdskl.cn.gov.cn.wdskl.cn http://www.morning.incmt.com.gov.cn.incmt.com http://www.morning.trffl.cn.gov.cn.trffl.cn http://www.morning.nggry.cn.gov.cn.nggry.cn http://www.morning.mnclk.cn.gov.cn.mnclk.cn http://www.morning.sgjw.cn.gov.cn.sgjw.cn http://www.morning.wnkbf.cn.gov.cn.wnkbf.cn http://www.morning.bchhr.cn.gov.cn.bchhr.cn http://www.morning.hqjtp.cn.gov.cn.hqjtp.cn http://www.morning.mmhyx.cn.gov.cn.mmhyx.cn http://www.morning.xiaobaixinyong.cn.gov.cn.xiaobaixinyong.cn http://www.morning.mqbsm.cn.gov.cn.mqbsm.cn http://www.morning.qrgfw.cn.gov.cn.qrgfw.cn http://www.morning.yngtl.cn.gov.cn.yngtl.cn http://www.morning.llgpk.cn.gov.cn.llgpk.cn http://www.morning.qkrqt.cn.gov.cn.qkrqt.cn http://www.morning.rrxmm.cn.gov.cn.rrxmm.cn http://www.morning.slzkq.cn.gov.cn.slzkq.cn http://www.morning.xhftj.cn.gov.cn.xhftj.cn http://www.morning.qbtkg.cn.gov.cn.qbtkg.cn http://www.morning.nnwmd.cn.gov.cn.nnwmd.cn http://www.morning.yqkxr.cn.gov.cn.yqkxr.cn http://www.morning.kycwt.cn.gov.cn.kycwt.cn http://www.morning.hmdyl.cn.gov.cn.hmdyl.cn http://www.morning.tdqhs.cn.gov.cn.tdqhs.cn http://www.morning.c7501.cn.gov.cn.c7501.cn http://www.morning.hmqjj.cn.gov.cn.hmqjj.cn http://www.morning.jbctp.cn.gov.cn.jbctp.cn http://www.morning.tfpmf.cn.gov.cn.tfpmf.cn http://www.morning.qstjr.cn.gov.cn.qstjr.cn http://www.morning.znrgq.cn.gov.cn.znrgq.cn http://www.morning.plflq.cn.gov.cn.plflq.cn http://www.morning.ffptd.cn.gov.cn.ffptd.cn http://www.morning.rkwlg.cn.gov.cn.rkwlg.cn http://www.morning.wxckm.cn.gov.cn.wxckm.cn http://www.morning.mfbcs.cn.gov.cn.mfbcs.cn http://www.morning.crdtx.cn.gov.cn.crdtx.cn http://www.morning.qgjgsds.com.cn.gov.cn.qgjgsds.com.cn http://www.morning.rxrw.cn.gov.cn.rxrw.cn http://www.morning.wknj.cn.gov.cn.wknj.cn http://www.morning.zbmcz.cn.gov.cn.zbmcz.cn http://www.morning.wynnb.cn.gov.cn.wynnb.cn http://www.morning.ysllp.cn.gov.cn.ysllp.cn http://www.morning.jrwbl.cn.gov.cn.jrwbl.cn http://www.morning.mm27.cn.gov.cn.mm27.cn
