greedyjob.cpp

任务时间表问题的贪心算法的代码,大家互相学习学习。

#include <iostream.h>
//#include "stdlib.h"


int GreedyJob(int n, int d[],int J[])
{
	   d[0]=0;	J[0]=0;	
        int k=1; J[1]=1; // k 为当前及时任务个数
        for (int i = 2; i <= n; i++){ 
			// 逐个加入任务
			 int r = k;	// r为任务i要加入的位置
             while( (d[J[r]]>d[i]) && (d[J[r]]!=r) ) // 搜索任务i要加入的位置
                 r = r-1;
             if ( (d[J[r]]<=d[i]) && (d[i]>r) )
			  {
				  // 如可以，加入任务i到及时任务集合
 				  for (int m = k; m >r; m--)
	    	           J[m+1]=J[m];
					   J[r+1]=i;
					   k=k+1;
              }   // end of if
        }  // end of first for
       return k;
}

void main()
{
	int i,n=7;
	int d[8]={0,4,2,4,3,1,4,6};
	int w[8]={0,70,60,50,40,30,20,10};
	int J[8]={0};
	int a=GreedyJob(n,d,J);

	cout<<"任务截止时间：";
	for(i=1;i<=n;i++)
		cout<<' '<<d[i]<<' '<<' ';
	cout<<endl;

	cout<<"任务误时惩罚：";
	for(i=1;i<=n;i++)
		cout<<' '<<w[i]<<' ';
	cout<<endl;

	cout<<"当前及时任务：";
	cout<<a<<endl;
	
	cout<<"任务最优排序：";
	for (i=1;i<=n;i++)
		cout<<' '<<J[i]<<' ';
	cout<<endl;
	int s=0;
    for (i=1;i<=n;i++)
		s=s+w[i]-w[J[i]];
	cout<<"最小务时惩罚为："<<s<<endl;
	
	
}