greedy.cpp

计算机算法设计与分析(王晓东)教材上相关源程序代码。 包括分治法(4)

template <class type>
void greedy(type *a,int n,int m)
{
	int i;
	if(n<=m)
	{
		cout<<" 为每个作业分配一台机器。"<<endl;
		return;
	}

	 sort(&a[1],n);



	MinHeap<machinenode> H(m);

	machinenode x;
	for(i=1;i<=m;i++)
	{
		x.avail=0;
		x.ID=i;
		H.Insert(x);
	}

	for(i=n;i>=1;i--)
	{
		H.DeleteMin(x);
		cout<<"将机器"<<x.ID<<"从"<<x.avail<<"到"
			<<(x.avail+a[i].time)<<"的时间段分配给作业"<<a[i].ID<<endl;

		x.avail+=a[i].time;
		H.Insert(x);
	}

	

}