独立任务最优调度-C++程序

=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpu独立任务最优调度问题【问题描述：】用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai≥bi，而对于某些j,j≠i，有ajbj。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例：(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。【编程任务】：对于给定的2台处理机A和B处理n个作业，找出一个最优调度方案，使2台机器处理完这n个作业的时间最短。【数据输入】：由文件input.txt提供输入数据。文件的第1行是1个正整数n,表示要处理n个作业。接下来的2行中，每行有n个正整数，分别表示处理机A和B处理第i个作业需要的处理时间。【结果输出】:程序运行结束时，将计算出的最短处理时间输出到文件output.txt中。=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpu【算法思路】：对于算法来说，没有最好，只有更好，算法的结果不一定是最佳答案，但至少是最接近最佳答案的。在权衡算法时间复杂度和空间复杂度的情况下，找到一个在时间和空间都能接受的算法才是上上之策。本例采样贪心算法的思想，但又不是严格意义上的贪心算法。思路：1）、把n个任务按一定规则分别存储到二维数组a[][]和b[][]中，规则，对任意i满足a[i][0]a[i][1]级数组a[][]存储在机器A上处理需要时间小于在机器B上处理时间的任务，数组B则相反。时间复杂度为O（n）。2）、对数组a[][]&b[][]排序：数组a[][]按a[i][0]的大小进行降序排列，对于a[i][0]==a[i+1][0]时按a[i][1]进行降序排列。同理数组b[][]。时间复杂度为O(NlogN)3）、优先使机器A&B分别处理数组A&B中的任务。4）、当A或B先处理好自己的时，在B或A还有剩余的整数个任务时再按照如下规则处理,首先把剩余的整数个任务按(s[i][0]-s[i][1])的大小进行生序排列，时间复杂度为O（NlogN）a）、若是A先于B处理完任务，则，则A优先选做间隔时间大的任务，可以理解无，节省的时间多。=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpub）、若是B先于A处理完任务，则，则B优先选做间隔时间小的任务，可以理解无，浪费的时间少。5）、计算机器A&B的处理时间，则最小处理时间ShortestTime=Max（TimeA,TimeB）6）、把ShortestTime导入到output.txt文件中。详细代码程序：//IndependentTask.h#ifndefINDEPENDENTTASK_H#defineINDEPENDENTTASK_HclassIndependentTask{public:IndependentTask();~IndependentTask();voidrun();//运行接口private:intnumber;//任务数量=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpuintcountA;//在机器A上用时间较少的任务个数intcountB;//在机器B上用时间较少的任务个数intShortestTime;//记录最短处理时间int**s;//存储number个任务在机器A&B的用时int**a;//存储在机器A上用时间较少的任务int**b;//存储在机器A上用时间较少的任务boolinput();//输入接口voidsort(int**s,inti,intj,intX);//快速排序X=0120-a[][]1--b[][]2--a[][]或b[][]voidOptimizationSorting(int**s,intlength,intX);//优化排序目的是降低处理时间和显示已排好序的数据//X=0--a[][]X=1---b[][]voidoutput();//输出显示};#endif=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpu//IndependentTask.cpp#includeiostream#includeiostream.h#includefstream#includefstream.h#includeIndependentTask.h#defineN50//预定义50个任务数根据实际问题大小来确定不要太大ifstreaminputFile(input.txt,ios::in);ofstreamoutputFile(output.txt,ios::out);IndependentTask::IndependentTask(){number=0;countA=0;countB=0;=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpuShortestTime=0;s=newint*[N];a=newint*[N];b=newint*[N];for(inti=0;iN;i++){s[i]=newint[2];a[i]=newint[2];b[i]=newint[2];}}IndependentTask::~IndependentTask(){for(inti=0;iN;i++){delete[]s[i];delete[]a[i];delete[]b[i];}=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpudelete[]s;delete[]a;delete[]b;}voidIndependentTask::run(){if(input()){sort(a,0,countA-1,0);sort(b,0,countB-1,1);OptimizationSorting(a,countA,0);OptimizationSorting(b,countB,1);output();}}boolIndependentTask::input(){inputFilenumber;outputFile总任务个数:numberendl;=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpufor(intj=0;j2;j++)//j==0时读取的是在机器A上作业用时{//j==1时读取的是在机器B上作业用时if(j==0){outputFile各个任务在机器A上处理用时为:;}else{outputFile各个任务在机器B上处理用时为:;}for(inti=0;inumber;i++){inputFiles[i][j];outputFiles[i][j];}outputFileendl;}outputFileendl;inputFile.close();=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpufor(inti=0;inumber;i++){if(s[i][0]s[i][1])//任务i在机器A上处理用时短{a[countA][0]=s[i][0];a[countA][1]=s[i][1];countA++;}else{b[countB][0]=s[i][0];b[countB][1]=s[i][1];countB++;}}//显示在机器A上处理用时少的任务outputFileendl以下任务在机器A上处理用时少:endl;for(j=0;j2;j++){=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpuif(j==0){outputFile在机器A上处理用时为:;}else{outputFile在机器B上处理用时为:;}for(inti=0;icountA;i++){outputFilea[i][j];}outputFileendl;}outputFileendl;//显示在机器B上处理用时少的任务outputFileendl以下任务在机器B上处理用时少:endl;for(j=0;j2;j++){if(j==0){=YXNpbHZtaW5nbGVp1304649833441&user_number_id=198246540&mytmenu=mdianpuoutputFile在机器A上处理用时为:;}else{outputFile在机器B上处理用时为:;}for(inti=0;icountB;i++){outputFileb[i][j];}outputFileendl;}outputFileendl;if(s!=NULL){if(a!=NULL||b!=NULL){returntrue;}retur