Job Sequencing With Deadline

Algorithm:

Step 1: Sort p[i] into non-increasing order. After sorting p[1]>= p[2]>=p[3]>=... p[i.]
Step 2: Add the next job i to the solution set if i can be completed by its deadline.
Assign i to time slot [r-1, r], where r is the largest integer such that 1 <= r <= d[i]
and [r-1, r] is free.
Step 3: Stop if all jobs are examined. Otherwise, go to step 2.

Time complexity: O(n^2)

Implementation:

Program In C

#include<conio.h>
#include<stdio.h>
int n,i,j,k,t;
int check(int s[],int p)
       {  int ptr=0;
           for(int i=0;i<n;i++)
           {if(s[i]==p)
               ptr++;
      }           
            if(ptr==0)
            return 1;
            else
            return 0;
        }    
                     
int main()
{  
     printf("enter the no of jobs      : ");
     scanf("%d",&n);
     int slot[n],profit,p[n],d[n];
     for(i=0;i<n;i++)
       {printf("\n enter the profit of job #%d      :",i+1);
       scanf("%d",&p[i]);                 
       printf("\n enter the deadline of job #%d    :",i+1);
       scanf("%d",&d[i]);
       }
      
     for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
         if(p[i]<p[j])
            { t=p[i];
              p[i]=p[j];
              p[j]=t;
              t=d[i];
              d[i]=d[j];
              d[j]=t;             
            }
              
       for(i=0;i<n;i++)
           slot[i]=0;         
                 
     for(i=0;i<n;i++)
         for(j=d[i];j>0;j--)
             {if(check(slot,j)==1)
                {slot[i]=j;
                break;} 
             }
           
     printf("\n\n INDEX   PROFIT  DEADLINE  SLOT ALLOTTED ");      
     for(i=0;i<n;i++)
     {if(slot[i]>0)
     printf("\n\n   %d       %d        %d        [%d - %d]", i+1,p[i],d[i],(slot[i]-1),slot[i]);
     else
     printf("\n\n   %d       %d        %d       REJECTED", i+1,p[i],d[i]);
     }
              
       getch();
}   

Program Code in C for Knapsack Problem

Algorithm


Step 1: Sort pi/wi into nonincreasing order.
Step 2: Put the objects into the knapsack according
to the sorted sequence as possible as we can.
e. g.
n = 3, M = 20, (p1, p2, p3) = (25, 24, 15)
(w1, w2, w3) = (18, 15, 10)
Sol: p1/w1 = 25/18 = 1.32
      p2/w2 = 24/15 = 1.6
      p3/w3 = 15/10 = 1.5
Optimal solution: x1 = 0, x2 = 1, x3 = 1/2
total profit = 24 + 7.5 = 31.5

Program In C

#include<conio.h>
#include<stdio.h>
int main()
{ int n,i;
float m,t;
printf("              capacity of knapsack      :   ");
scanf("%f",&m);
  printf("              no of elements            :   ");
  scanf("%d",&n);
  printf("\n                    INPUT DATA \n");
  float profit=0,f[n],r[n],pf[n],p[n],w[n];
  for(i=0;i<n;i++)
  {
   printf("              profit of Element No%d  :  ",i+1);
   scanf("%f",&p[i]);
   printf("              weignt of Element No%d  :  ",i+1);
   scanf("%f",&w[i]);
  }
 
  printf("\n\n");
 
  for( i=0;i<n;i++)
      r[i]=(p[i]/w[i]);
  for( i=0;i<n;i++)
      printf("       profit to weight ratio for %d Element is %f \n",i+1,r[i]) ;
  printf("\n\n");   
  for(int i=0;i<n;i++)
      for(int j=i+1;j<n;j++)
         {if(r[j]>r[i])
             {t=r[j];
              r[j]=r[i];
              r[i]=t;
              t=p[j];
              p[j]=p[i];
              p[i]=t;
               t=w[j];
              w[j]=w[i];
              w[i]=t;    
             }
         }
        
        
        
         for(i=0;i<n;i++)
         { if(w[i]<=m)
             { m-=w[i];
               f[i]=1;
               pf[i]=p[i]*f[i];
               profit+=pf[i];
             }
            
           else if(m<w[i] && m>0)
             {
               pf[i]=(p[i]*m/w[i]);
               profit+=pf[i];
               f[i]=m/w[i];
                m=0;
             } 
           else
           {f[i]=0;
            pf[i]=0;
            } 
         }    
              
   
    printf("       profit given      weight given       fraction taken      profit earned \n\n");
    for(int i=0;i<n;i++)
     printf("       %f            %f         %f            %f       \n",p[i],w[i],f[i],pf[i]);
    
     printf("\n\n\n       TOTAL PROFIT IS : %f",profit);                                                                                             
   getch();  
}