设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理。作业i所需时间为ti. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业执行次序,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
要求:随机生成n个作业相关信息,并计算由m台机器处理的最短时间。
//*多机调度问题:贪心算法求解 //将作业时长的时长进行降序排序,然后按照排序好的顺序将作业分配给空闲的机器 int m,n;//机器数和作业数 int work[1000];//作业需要处理的时间存储 int machine[1000];//机器数 # include<bits/stdc++.h>//包含C++中包含的所有头文件 using namespace std; bool cmp(int a,int b) { return a>b; } void working() { //每次都是往处理作业时间最少的机器上面放 for(int i=m+1;i<=n;i++){ machine[m]+=work[i];//机器现在的总工作时间 sort(machine+1,machine+1+m,cmp);//进行降序排序 ,以machine数组的第一个数为排序区间下界,第二个参数以machine数组中最后一个数排序期间的上界,这样第一个机器就是用时最长的 }//sort(a+1,a+1+n) } int main() { int t; cin>>t;//进行几次实验 for(int k=1;k<=t;k++) { cin>>n>>m;//输入机器数和作业数 for(int i=1;i<=n;i++) cin>>work[i];//输入作业时长 sort(work+1,work+n+1,cmp); //进行降序排序 for(int j=1;j<=m;j++) { machine[j]=work[j]; work[j]=0; } working(); cout<<"Case "<<k<<": "<<machine[1]<<endl; } }
在本次实验中,出现了地址标与第一个数字的对应问题,如共有n个作业,其对应下标应该为a[n-1],使得在将作业时长数加到机器现有时长数时出现了问题;刚开始认为第一个机器的总时长数就是改组工作数据中的最短时长,结果证明并不是如此,因此对机器的时长数进行了排序,最大的即为最长的,也就是该项活动的最优解;并没有对作业时长进行排序,按照一上来的顺序进行了优先分配,发现没有该项实验没有先到优先原则,可以有更优解,通过实操发现降序排序结果最佳。