C codes for Greedy Algorithms

                        

              Job Sequencing using Greedy method in C

 

#include<stdio.h>

#define MAX 100

typedef struct Job {

  char id[6];

  int deadline;

  int profit;

} Job;

void JobSeq(Job jobs[], int n);

// minimum of two jobs.

int Min(int x, int y) {

  if(x < y) return x;

  return y;

}

int main(void) {

  /*variables*/

  int i, j;

  /*jobs with deadline and profit*/

  Job jobs[6] = {

    {"j1", 60,  200},

    {"j2", 40,  180},

    {"j3", 30,  190},

    {"j4", 20,  300},

    {"j5", 40,  120},

    {"j6", 70,  120},

  };

  /*need one temp variable*/

  Job temp;

  //total  jobs

  int n = 6;

   /*sort profit  in descending order*/

  for(i = 1; i < n; i++) {

    for(j = 0; j < n - i; j++) {

      if(jobs[j+1].profit > jobs[j].profit) {

        temp = jobs[j+1];

        jobs[j+1] = jobs[j];

        jobs[j] = temp;  //

      }

    }

  }

  printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");

  for(i = 0; i < n; i++) {

    printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);

  }

  JobSeq(jobs, n);

  return 0;

}

void JobSeq(Job jobs[], int n) {

    /*variables*/

  int i, j, k, maxprofit;

  //free time slots

  int timeslot[MAX];

  //filled time slots

  int filledTimeSlot = 0;

  //find max deadline value

  int dmax = 0;

  for(i = 0; i < n; i++) {

    if(jobs[i].deadline > dmax) {

      dmax = jobs[i].deadline;

    }

  }

  //Initially let us keep all free empty slot as -1

  for(i = 1; i <= dmax; i++) {

    timeslot[i] = -1;

  }

  printf("dmax: %d\n", dmax);

  for(i = 1; i <= n; i++) {

    k = Min(dmax, jobs[i - 1].deadline);

    while(k >= 1) {

      if(timeslot[k] == -1) {

        timeslot[k] = i-1;

        filledTimeSlot++;

        break;

      }

      k--;

    }

    //if all time slots are filled then stop

    if(filledTimeSlot == dmax) {

      break;

    }

  }

   /*Sequenced jobs*/

  printf("\nSequenced Jobs: ");

  for(i = 1; i <= dmax; i++) {

    printf("%s", jobs[timeslot[i]].id);

    if(i < dmax) {

      printf(" --> ");

    }

  }

  // profit

  maxprofit = 0;

  for(i = 1; i <= dmax; i++) {

    maxprofit += jobs[timeslot[i]].profit;

  }

  printf("\nMax Profit: %d\n", maxprofit);

}

   Binary Search using recursion in C

  #include <stdio.h>

void BinSearch(int [], int, int, int);

void SortAscending(int [], int);

 

int main()

{

    int key, size, i;

    int list[25];

 

    printf("Enter size of a list: ");

    scanf("%d", &size);

    printf("Enter elements\n");

    for(i = 0; i < size; i++)

    {

        scanf("%d",&list[i]);

    }

    SortAscending(list, size);

    printf("\n");

    printf("Enter key to search\n");

    scanf("%d", &key);

    BinSearch(list, 0, size, key);

 

}

void SortAscending(int list[], int size)

{

    int temp, i, j;

    for (i = 0; i < size; i++)

    {

        for (j = i; j < size; j++)

        {

            if (list[i] > list[j])

            {

                temp = list[i];

                list[i] = list[j];

                list[j] = temp;

            }

        }

    }

}

void BinSearch(int list[], int lo, int hi, int key)

{

    int mid;

    if (lo > hi)

    {

        printf("Key not found\n");

        return;

    }

    mid = (lo + hi)/2;

    if (list[mid] == key)

    {

        printf("Key found\n");

    }

    else if (list[mid] > key)

    {

        BinSearch(list, lo, mid - 1, key);

    }

    else if (list[mid] < key)

    {

        BinSearch(list, mid + 1, hi, key);

    }

}

  Job sequencing using Greedy & recursion in C

 #include<stdio.h>

#define MAX 100

typedef struct Job {

  char id[6];

  int deadline;

  int profit;

} Job;

void JobSeq(Job jobs[], int n);

// minimum of two jobs.

int Min(int x, int y) {

  if(x < y) return x;

  return y;

}

int main(void) {

   /*variables*/

  int i, j;

   /*jobs with deadline and profit*/

  Job jobs[6] = {

    {"j1", 60,  200},

    {"j2", 40,  180},

    {"j3", 30,  190},

    {"j4", 20,  300},

    {"j5", 40,  120},

    {"j6", 70,  120},

  };

   /*need one temp variable*/

  Job temp;

  //total  jobs

  int n = 6;

   /*sort profit  in descending order*/

  for(i = 1; i < n; i++) {

    for(j = 0; j < n - i; j++) {

      if(jobs[j+1].profit > jobs[j].profit) {

        temp = jobs[j+1];

        jobs[j+1] = jobs[j];

        jobs[j] = temp;  //

      }

    }

  }

  printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");

  for(i = 0; i < n; i++) {

    printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);

  }

  JobSeq(jobs, n);

  return 0;

}

void JobSeq(Job jobs[], int n) {

     /*variables*/

  int i, j, k, maxprofit;

  //free time slots

  int timeslot[MAX];

  //filled time slots

  int filledTimeSlot = 0;

  //find max deadline value

  int dmax = 0;

  for(i = 0; i < n; i++) {

    if(jobs[i].deadline > dmax) {

      dmax = jobs[i].deadline;

    }

  }

  //Initially let us keep all free empty slot as -1

  for(i = 1; i <= dmax; i++) {

    timeslot[i] = -1;

  }

  printf("dmax: %d\n", dmax);

  for(i = 1; i <= n; i++) {

    k = Min(dmax, jobs[i - 1].deadline);

    while(k >= 1) {

      if(timeslot[k] == -1) {

        timeslot[k] = i-1;

        filledTimeSlot++;

        break;

      }

      k--;

    }

    //if all time slots are filled then stop

    if(filledTimeSlot == dmax) {

      break;

    }

  }

   /*Sequenced jobs*/

  printf("\nSequenced Jobs: ");

  for(i = 1; i <= dmax; i++) {

    printf("%s", jobs[timeslot[i]].id);

    if(i < dmax) {

      printf(" --> ");

    }

  }

  // profit

  maxprofit = 0;

  for(i = 1; i <= dmax; i++) {

    maxprofit += jobs[timeslot[i]].profit;

  }

  printf("\nMax Profit: %d\n", maxprofit);

}

 Knapsack solution using  Greedy in C

 # include<stdio.h>

 void GreedKPSK(int n, float weight[], float profit[], float CaP) {

   float x[20], tp = 0;

   int i, j, u;

   u = CaP;

 

   for (i = 0; i < n; i++)

      x[i] = 0.0;

 

   for (i = 0; i < n; i++) {

      if (weight[i] > u)

         break;

      else {

         x[i] = 1.0;

         tp = tp + profit[i];

         u = u - weight[i];

      }

   }

 

   if (i < n)

      x[i] = u / weight[i];

 

   tp = tp + (x[i] * profit[i]);

 

   printf("\nThe result vector is:- ");

   for (i = 0; i < n; i++)

      printf("%f\t", x[i]);

 

   printf("\nMaximum profit is:- %f", tp);

 

}

 

int main() {

   float weight[20], profit[20], CaP;

   int num, i, j;

   float ratio[20], temp;

 

   printf("\nEnter the no. of objects:- ");

   scanf("%d", &num);

    printf("\nEnter the wts and profits of each object:- ");

   for (i = 0; i < num; i++) {

      scanf("%f %f", &weight[i], &profit[i]);

   }

 

   printf("\nEnter the CaPacity of GreedKPSK:- ");

   scanf("%f", &CaP);

 

   for (i = 0; i < num; i++) {

      ratio[i] = profit[i] / weight[i];

   }

    for (i = 0; i < num; i++) {

      for (j = i + 1; j < num; j++) {

         if (ratio[i] < ratio[j]) {

            temp = ratio[j];

            ratio[j] = ratio[i];

            ratio[i] = temp;

 

            temp = weight[j];

            weight[j] = weight[i];

            weight[i] = temp;

             temp = profit[j];

            profit[j] = profit[i];

            profit[i] = temp;

         }

      }

   }

 

   GreedKPSK(num, weight, profit, CaP);

   return(0);

}