The BOTTOM LINE Quote Of The Day

The BOTTOM LINE Quote Of The Day

Don't Ever Tell GOD How BIG Your Problems are.
Just Tell Your Problems How BIG your GOD is ;)

Thursday, April 26, 2012

Job Sequencing Problem


#include<conio.h>
#include<stdio.h>
#define max 20
#define limit -1

struct job
{
 int jno;
 int pr;    
 int ddl;    
}jb[max],tmp;

int seq[max];
int ss;

int size;

void inp_dat()
{
  printf("\n Enter the no. of Job : ");
  scanf("%d",&size);

  for(int i=0;i<size;i++)
  {
    jb[i].jno = i+1;
    printf("\n Enter Profit and Deadline of Job#%d : ",jb[i].jno);
    scanf("%d %d",&jb[i].pr,&jb[i].ddl);      
  }  
}

void disp_dat()
{
  for(int i=0;i<size;i++)
  {
    printf("\n\n\t Job#%d :",jb[i].jno);
    printf("\n Profit : %d",jb[i].pr);
    printf("\t Deadline : %d",jb[i].ddl);    
  }  

}

void Job_Seq()
{
  int i,j,temp;
  printf("\n\n Sorting Jobs in the decreasing order of Profit");
  int min = limit;
  int tpr = 0;
  ss = 0;
  for(i=0;i<size;i++)
  {
    for(j=0;j<size-i-1;j++)
    {
      if(jb[j].pr < jb[j+1].pr)
      {
        tmp = jb[j];
        jb[j] = jb[j+1];
        jb[j+1] = tmp;        
      }
    }
  }
 

 disp_dat();
 
 for(i=0;i<size;i++)
 {
   if(min < jb[i].ddl || ss+1 <= min)
   {
      seq[ss] = jb[i].jno;
      tpr += jb[i].pr;
      ss++;    
      if(min <= jb[i].ddl)
        min = jb[i].ddl;
      else
      {
        temp = seq[ss-1];
        for(j=ss-1;j>0;j--)
         seq[j] = seq[j-1];
        seq[0] = temp;
      }
     
   }                    
 }  

 printf("\n The Job Sequence is :");
 for(i=0;i<ss;i++)
  printf(" %d",seq[i]);
 printf("\n\n Total Maximum Profit : %d",tpr);
}

int main()
{
 inp_dat();  
 Job_Seq();
 getch();
 return 0;
}

No comments:

Post a Comment