tanxin.cpp

来自「这是算法中一个经典问题。利用贪心算法实现一个更快的 作业排序问题」· C++ 代码 · 共 143 行

#include <stdio.h > 
#include <iostream.h>      
#include <malloc.h >          
int MAX(int  *D,int i, int j); 
int FIND(int *parent,int i);  
int MIN(int  n,int  m) ;
int FJS(int *D,int n,int  b,int  *J,int *Q) ;
void UNION(int *parent,int i,int j);
void Insertionsort(int  *D,int n) ;                
    void  main()       
    {       
    int *D,*J,*Q,*p,n,b,i,k;       
    cout<<"用贪心法解决一种更快作业排序问题 "<<endl;       
    cout<<"请输入作业的数目: ";       
    cin>>n;       
    D=(int*)malloc((n+1)*sizeof(int));       
    p=(int*)malloc((n+1)*sizeof(int));       
    cout<< "\n请输入每个作业的效益值("<<n<<"个): ";       
    for(i=1;i <=n;i++)       
    cin>>p[i];       
    Insertionsort(p,n);       
    cout<< "\n按效益值非增排序后各作业为:\n ";       
    cout<< "\n作业序号                                       效益值\n ";       
    for(i=1;i <=n;i++)       
    cout<<"J"<<i<<"                                             "<<p[i] <<endl;    
    cout<<"请输入按效益值非增排序后各作业的截止时间("<<n<<"个): ";       
    for(i=1;i <=n;i++)       
    cin>>D[i];       
    b=MIN(n,MAX(D,1,n));       
    J=(int*)malloc((b+1)*sizeof(int));       
    Q=(int*)malloc((b+1)*sizeof(int));       
    for(i=1;i <=b;i++)       
    Q[i]=-1;       
    k=FJS(D,n,b,J,Q);       
    cout<< "\n本问题的最优解\n ";       
    cout<< "\n作业序号                                       效益值\n ";       
    for(i=1;i <=k;i++)       
    cout<<"J"<<J[i]<<"                                          "<<p[J[i]] <<endl;        
    cout<< "\n各作业的执行次序\n ";       
    cout<< "\n作业序号                                       效益值\n ";       
    for(i=1;i <=b;i++)       
    if(Q[i]!=-1)       
    cout<<"J"<<Q[i]<<"                                                               "<<p[Q[i]]<<endl;               
 }       
int  FIND(int *parent,int i)       
    {//查找含有元素i的树根，使用压缩规则去压缩由i到根j的所有结点       
    int j,k,t;       
    j=i;       
    while(parent[j] >0)  j=parent[j];//找根       
    k=i;       
    while(k!=j){//压缩由i到根j的结点       
    t=parent[k];       
    parent[k]=j;       
    k=t;       
    }       
    return j;       
    }       
        
    void  UNION(int *parent,int i,int j)       
    {//使用加权规则合并根为i和j的两个集合       
    int x;       
    x=parent[i]+parent[j];       
    if(parent[i] >parent[j]){//i的结点少       
    parent[i]=j;       
    parent[j]=x;       
    }       
    else{//j的结点少       
    parent[j]=i;       
    parent[i]=x;       
    }       
    }       
        
    int MIN(int  n,int  m)                                                                                                               
    {//求n和m的最小值       
    if(n >m)   return  m;       
    else return  n;       
    }       
    
	
	void Insertionsort(int  *D,int n)       
    {//将D中的元素按非增次序分类       
    int j,item,i;       
    D[0]=65525;       //设置监视      
    for(j=2;j <=n;j++){       
    item=D[j];       
    i=j-1;       
    while(item >D[i]){       
    D[i+1]=D[i];       
    i=i-1;       
    }       
    D[i+1]=item;             
    }           
    } 

    int  FJS(int *D,int n,int  b,int  *J,int *Q)       
    {//找J(n)的最优解，并返回最优解的个数       
    int i,*F,*p,j,l,m,k;       
    F=(int *)malloc((b+1)*sizeof(int));       
    p=(int *)malloc((b+1)*sizeof(int));       
   for(i=0;i <=b;i++){//将树置初值       
    F[i]=i;       
    p[i]=-1;       
    }       
    k=0;//初始化J       
    for(i=1;i <=n;i++)       
    {//使用贪心规则       
    j=FIND(p,MIN(n,D[i]));       
    if(F[j]!=0)       
    {//选择作业i       
    k=k+1;       
    J[k]=i;       
    Q[F[j]]=i;       
    m=F[j];       
    l=FIND(p,F[j]-1);       
    UNION(p,l,j);       
    F[j]=F[l];       
    }       
    }       
    return       k;//返回最优解的个数       
    }            
    int  MAXMUM(int   i,int  j)       
    {//求i和j的最大值       
    if(i >j)  return  i;       
    else   return j;       
    }       
        
    int MAX(int  *D,int i, int j)       
    {//D(1:n)是含有n个元素数组，求出D(i,j)中的最大值并返回       
    int  max,mid,max1,max2;       
    if(i==j)  max=D[i];       
    else       
    if(i==j-1)               
    if(D[i] <D[j]) max=D[j];       
    else   max=D[i];       
    else{       
    mid=(i+j)/2;       
    max1=MAX(D,i,mid);       
    max2=MAX(D,mid+1,j);       
    max=MAXMUM(max1,max2);       
    }       
    return max;       
    }