带有限期的作业排序.cpp

带有期限的作业排序问题：假定只能在一台机器上处理n个作业

//贪心算法之带有限期的作业排序
//程序源代码
#include<iostream.h>
#define MAX 100
int n;                                         //作业数 
template<class T>                              //定义模板   
class Sample                                   //定义Sample为类模板
{
	T p[MAX];                                  //数组p中的元素是完成每个作业可获得的效益值
	int d[MAX],x[MAX],z[MAX];                  //d中是期限值，x是解向量，z中记录的是序号
	public:
	    Sample(){n=0;}
		void getdata();                        //数据输入函数
		int  max();                            //求最大值函数  
		void sort();                           //排序函数
        void greedyjs();                       //带有限期的作业排序函数
		void display();                        //结果输出函数
		T sum();                               //求和
};
		template<class T>
		void Sample<T>::getdata ()             //数据输入
		{
			cout<<"作业数：";
			cin>>n;
			for (int i=1;i<=n;i++)
			{
				z[i]=i; 
				cout<<"第"<<i<<"个作业的截止期限为：";
				cin>>d[i];
				cout<<endl;
			}
            for (int j=1;j<=n;j++)
			{
				cout<<"第"<<j<<"个作业的效益值为：";
				cin>>p[j];
				cout<<endl;
			}
		}
		template<class T>
		void Sample<T>::sort()                 //按完成作业可获得的效益值大小的非增次序  
		{                                      //排序 
			int i,j,k,temp2;
			T temp1;
			for (i=1;i<=n-1;i++)
				for(j=i+1;j<=n;j++)
				{
					if(p[i]<p[j])
					{
						temp1=p[i];            //对于每一个作业，它的期限和序号也要一起
						temp2=d[i];            //参加排序，以保证相互的对应
						k=z[i];
						p[i]=p[j];
						d[i]=d[j];
						z[i]=z[j];
						p[j]=temp1;
						d[j]=temp2;
						z[j]=k;
					}
				}
            cout<<"所有作业按效益值从大到小排序结果为(效益，期限，序号)："<<endl;
              for (i=1;i<=n;i++)
			       cout<<"("<<p[i]<<","<<d[i]<<","<<z[i]<<")"<<" ";
		   cout<<endl;        
		}
		template<class T>
		void Sample<T>::greedyjs()             //求解带有限期的作业排序问题   
		{
			int i,k,l,r;
			d[0]=x[0]=0;                       //初始化 
			k=1;
			x[1]=1;                            //计入作业1
			for (i=2;i<=n;i++)                 //处理作业i，找i的位置并检查插入的可能性
			{
				r=k;
				while(d[x[r]]>d[i] && d[x[r]]!=r)
					r=r-1;
				if (d[x[r]]<=d[i] && d[i]>r)
				{
					for (l=k;l>=r+1;l--)
						x[l+1]=x[l];
					x[r+1]=i;                  //把i插入解向量x中 
                    k=k+1;
				}
			}
		}
        template<class T>
        int  Sample<T>::max()                  //求最大的期限
		{
			int i,temp;
			for (i=2;i<=n;i++)
				if (d[i]<=d[i-1])
				{
					temp=d[i];
					d[i]=d[i-1];
					d[i-1]=temp;
				}
            return d[n];
		}
		template<class T>
		void Sample<T>::display()              //结果输出
		{
 			int i;
		    for (i=1;i<=max();i++)
			     cout<<z[x[i]]<<" ";           //解向量与序号保持一致
		      cout<<endl;
		}
		template<class T>
		T Sample<T>::sum()                     //求和
		{
			int i,sum;
			sum=0;
			for (i=1;i<=max();i++)
				sum+=p[i];
			return sum;
		}
         void main()                           //主函数
		 {
			Sample<int> s;                     //声明一个模板类的对象s
			s.getdata();                       //通过访问对象的公有成员函数，实现数据输入
			s.sort();                          //排序
			s.greedyjs();                      //求解带有限期的作业排序问题
			cout<<"带有限期和效益的单位时间的作业排序问题的最优解为：";
			s.max();
			s.display();                       //输出最优解
			cout<<"可获得的最大效益值为："<<s.sum()<<endl;      //输出最大效益值
		 }