//貪心算法之帶有限期的作業(yè)排序
//程序源代碼
#include<iostream.h>
#define MAX 100
int n;                                         //作業(yè)數(shù) 
template<class T>                              //定義模板   
class Sample                                   //定義Sample為類模板
{
	T p[MAX];                                  //數(shù)組p中的元素是完成每個(gè)作業(yè)可獲得的效益值
	int d[MAX],x[MAX],z[MAX];                  //d中是期限值，x是解向量，z中記錄的是序號(hào)
	public:
	    Sample(){n=0;}
		void getdata();                        //數(shù)據(jù)輸入函數(shù)
		int  max();                            //求最大值函數(shù)  
		void sort();                           //排序函數(shù)
        void greedyjs();                       //帶有限期的作業(yè)排序函數(shù)
		void display();                        //結(jié)果輸出函數(shù)
		T sum();                               //求和
};
		template<class T>
		void Sample<T>::getdata ()             //數(shù)據(jù)輸入
		{
			cout<<"作業(yè)數(shù)：";
			cin>>n;
			for (int i=1;i<=n;i++)
			{
				z[i]=i; 
				cout<<"第"<<i<<"個(gè)作業(yè)的截止期限為：";
				cin>>d[i];
				cout<<endl;
			}
            for (int j=1;j<=n;j++)
			{
				cout<<"第"<<j<<"個(gè)作業(yè)的效益值為：";
				cin>>p[j];
				cout<<endl;
			}
		}
		template<class T>
		void Sample<T>::sort()                 //按完成作業(yè)可獲得的效益值大小的非增次序  
		{                                      //排序 
			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];            //對于每一個(gè)作業(yè)，它的期限和序號(hào)也要一起
						temp2=d[i];            //參加排序，以保證相互的對應(yīng)
						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<<"所有作業(yè)按效益值從大到小排序結(jié)果為(效益，期限，序號(hào))："<<endl;
              for (i=1;i<=n;i++)
			       cout<<"("<<p[i]<<","<<d[i]<<","<<z[i]<<")"<<" ";
		   cout<<endl;        
		}
		template<class T>
		void Sample<T>::greedyjs()             //求解帶有限期的作業(yè)排序問題   
		{
			int i,k,l,r;
			d[0]=x[0]=0;                       //初始化 
			k=1;
			x[1]=1;                            //計(jì)入作業(yè)1
			for (i=2;i<=n;i++)                 //處理作業(yè)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()              //結(jié)果輸出
		{
 			int i;
		    for (i=1;i<=max();i++)
			     cout<<z[x[i]]<<" ";           //解向量與序號(hào)保持一致
		      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()                           //主函數(shù)
		 {
			Sample<int> s;                     //聲明一個(gè)模板類的對象s
			s.getdata();                       //通過訪問對象的公有成員函數(shù)，實(shí)現(xiàn)數(shù)據(jù)輸入
			s.sort();                          //排序
			s.greedyjs();                      //求解帶有限期的作業(yè)排序問題
			cout<<"帶有限期和效益的單位時(shí)間的作業(yè)排序問題的最優(yōu)解為：";
			s.max();
			s.display();                       //輸出最優(yōu)解
			cout<<"可獲得的最大效益值為："<<s.sum()<<endl;      //輸出最大效益值
		 }