多機調度問題的Java實現（貪心算法）
具體問題描述以及C/C++實現參見網址
[java]?view?plain?copy?print?import?java.util.ArrayList;?
import?java.util.Collections;?
import?java.util.LinkedList;?
import?java.util.List;?
/**?
*?多機調度問題--貪心算法? *?@author?Lican? *? */?public?class?JobMachine?{?
public?static?class?JobNode?implements?Comparable{?
int?id;//作業的標號?
int?time;//作業時間?
public?JobNode(int?id,int?time){?
this.id=id;?
this.time=time;?
}?
@Override?
public?int?compareTo(Object?x)?{//按時間從大到小排列?
int?times=((JobNode)x).time;?
if(time>times)?return?-1;?
if(time==times)?return?0;?
return?1;?
}?
}?
public?static?class?MachineNode?implements?Comparable{?
int?id;//機器的標號?
int?avail;//機器空閑的時間（即機器做完某壹項工作的時間）?
public?MachineNode(int?id,int?avail){?
this.id=id;?
this.avail=avail;?
}?
@Override?
public?int?compareTo(Object?o)?{//升序排序，LinkedList的first為最小的?
int?xs=((MachineNode)o).avail;?
if(avail<xs)?return?-1;?
if(avail==xs)?return?0;?
return?1;?
}?
}?
public?static?int?greedy(int[]?a?,int?m){?
int?n=a.length-1;//a的下標從1開始，所以n（作業的數目）=a.length-1?
int?sum=0;?
if(n<=m){?
for(int?i=0;i<n;i++)?
sum+=a[i+1];?
System.out.println("為每個作業分別分配壹臺機器");?
return?sum;?
}?
List<JobNode>?d=new?ArrayList<JobNode>();//d保存所有的作業?
for(int?i=0;i<n;i++){//將所有的作業存入List中，每壹項包含標號和時間?
JobNode?jb=new?JobNode(i+1,a[i+1]);?
d.add(jb);?
}?
Collections.sort(d);//對作業的List進行排序?
LinkedList<MachineNode>?h=new?LinkedList<MachineNode>();//h保存所有的機器?
for(int?i=1;i<=m;i++){//將所有的機器存入LinkedList中?
MachineNode?x=new?MachineNode(i,0);//初始時，每臺機器的空閑時間（完成上壹個作業的時間）都為0?
h.add(x);?
}?
int?test=h.size();?
for(int?i=0;i<n;i++){?
Collections.sort(h);?
MachineNode?x=h.peek();?
System.out.println("將機器"+x.id+"從"+x.avail+"到"+(x.avail+d.get(i).time)+"的時間段分配給作業"+d.get(i).id);?
x.avail+=d.get(i).time;?
sum=x.avail;?
}?
return?sum;?
}?
public?static?void?main(String[]?args)?{?
int[]?a={0,2,14,4,16,6,5,3};?
int?m=3;?
int?sum=greedy(a,m);?
System.out.println("總時間為："+sum);?
}?
}?
/**?
運行結果：?將機器1從0到16的時間段分配給作業4?
將機器2從0到14的時間段分配給作業2?
將機器3從0到6的時間段分配給作業5?
將機器3從6到11的時間段分配給作業6?
將機器3從11到15的時間段分配給作業3?
將機器2從14到17的時間段分配給作業7?
將機器3從15到17的時間段分配給作業1?
總時間為：17?
*/