贪心算法

流水作业调度问题

问题引入

有n个作业要在两台机器M₁和M₂组成的流水线上完成加工。每个作业i 都必须先花时间a_i 在M₁上加工，然后花时间b_i 在M₂上加工。 求解n个作业的加工顺序，使得总的加工时间最短。

问题分析

最优调度： 让M₁没有空闲， M₂的空闲时间尽量短。 设S₁ 为 a < b的作业集合，S₂为 a >= b 的作业集合，将S₁的作业按a 递增序排序，S₂ 中的作业按照b 递减序排序，则最优顺序为 S₁(排序后) + S₂（排序后）

加工生产调度

某工厂收到了n个产品的订单，这n个产品分别需用A,B两台机床加工，并且必须先在A机床加工后才可以送到B机床加工。 某个产品i在A,B两机床加工的时间分别为Ai，Bi。怎样安排这n个产品的加工顺序，才能使总的加工时间最短？这里所说的加工时间是指：从开始加工第一个产品到所有的产品都已在A,B两台机床加工完毕的时间。 【输入格式】： 第一行仅一个数据n，表示产品的数量。（0<n<1000） 接下来n个数据是表示这n个产品在A机床加工，各自所要的时间（都是整数） 最后的n个数据是表示这n个产品在B机床加工，各自所要的时间（都是整数） 【输出格式】： 第一行一个数据，表示最短的加工时间。 第二行是一种用时最短的产品加工顺序。 样例输入： 5 3 5 8 7 10 6 2 1 4 9 样例输出 34 1 5 4 2 3

贪心策略: 设 E_i = min{a_i,b_i}。并构建最优作业加工顺序集合 S = { }。 将E按照从小到大的顺序排序，然后从第1个开始处理，若 E_i = a_i ，则将它排在S集合从头开始的作业后面，若无首作业，则它就成为S的首作业，若 E_i = b_i , 则将它排在从尾开始的作业前面，若无尾作业，则它成为S的尾作业。

//参考程序 #include<iostream> using namespace std; int ans[1005],n,k,i,j,t,a[1005]; int b[1005],m[1005],s[1005]; void Read(); void Solve(); int main(){ Read(); Solve(); return 0; } void Read() { int i; cin >> n; for(i=1;i<=n;i++) cin >> a[i]; for(i=1;i<=n;i++) cin >> b[i]; } void Solve() { for(i=1;i<=n;i++){ m[i]=min(a[i],b[i]); s[i]=i; } for(i =1;i <= n-1; i++)//按产品的加工顺序从小到大排序 for(j = i+1; j <= n; j++) if(m[i]>m[j]) { swap(m[i],m[j]); swap(s[i],s[j]); } k=0; t= n+1; for(i=1;i<=n;i++)//安排产品的加工顺序 if(m[i]== a[s[i]]){ k++; ans[k]=s[i]; }else{ t--; ans[t]=s[i]; } t=0;k=0;//k为A加工时间，t为B加工时间 for(i=1; i <= n; i++)//模拟计算最少加工时间 { k+= a[ans[i]]; if(t < k) t=k; t += b[ans[i]]; } cout << t << endl; for(i =1; i<=n;i++) cout << ans[i] << " "; cout << endl; }