|
|
The complete code (C language):
#include <stdio.h>
#include <malloc.h>
int FIND (int * parent, int i)
{// Find the root of the tree containing element i, and use compression rules to compress all nodes from i to root j
int j, k, t;
j = i;
while (parent [j]> 0) j = parent [j]; // Find the root
k = i;
while (k! = j) {// compress the node from i to root j
t = parent [k];
parent [k] = j;
k = t;
}
return j;
}
void UNION (int * parent, int i, int j)
{// Merge two sets of roots i and j using weighting rules
int x;
x = parent [i] + parent [j];
if (parent [i]> parent [j]) {// i has fewer nodes
parent [i] = j;
parent [j] = x;
}
else {// j has fewer nodes
parent [j] = i;
parent [i] = x;
}
}
int MIN (int n, int m)
{// Find the minimum of n and m
if (n> m) return m;
else return n;
}
int FJS (int * D, int n, int b, int * J, int * Q)
{// Find the optimal solution of J (n), and return the number of optimal solutions
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 ++) {// set the tree to its initial value
F [i] = i;
p [i] =-1;
}
k = 0; // initialize J
for (i = 1; i <= n; i ++)
{// Use greedy rules
j = FIND (p, MIN (n, D [i]));
if (F [j]! = 0)
{// Choose job 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; // Return the number of optimal solutions
}
int MAXMUM (int i, int j)
{// Find the maximum of i and j
if (i> j) return i;
else return j;
}
int MAX (int * D, int i, int j)
{// D (1: n) is an array of n elements, find the maximum value in D (i, j) and return
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;
}
void Insertionsort (int * D, int n)
{// Classify the elements in D in non-increasing order
int j, item, i;
D [0] = 65525; // Set watchpoint
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;
}
}
void main ()
{
int * D, * J, * Q, * p, n, b, i, k;
printf ("\n ******************* Use greedy method to solve the problem of job sequencing with a finite period of time ********\n ");
printf ("\n Please enter the number of jobs:\n");
scanf ("% d",&n);
D = (int *) malloc ((n + 1) * sizeof (int));
p = (int *) malloc ((n + 1) * sizeof (int));
printf ("\n Please enter the benefit value of each job (% d):", n);
for (i = 1; i <= n; i ++)
scanf ("% d",&p [i]);
Insertionsort (p, n);
printf ("\n each job after non-increasing order by benefit value:\n");
printf ("\n job serial number benefit value\n");
for (i = 1; i <= n; i ++)
printf ("J% d% d\n", i, p [i]);
printf ("\n");
printf ("\n, please enter the deadline for each job after non-increasing order of benefits (% d):", n);
for (i = 1; i <= n; i ++)
scanf ("% d",&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);
printf ("\n\n ************************ The optimal solution for this problem **************** *************\n\n ");
printf ("\n job serial number benefit value\n");
for (i = 1; i <= k; i ++)
printf ("J% d% d\n", J [i], p [i]);
printf ("\n\n ************************ The execution order of each job ***************** *************\n ");
printf ("\n job serial number benefit value\n");
for (i = 1; i <= b; i ++)
if (Q [i]! =-1)
printf ("J% d% d\n", Q [i], p [i]);
printf ("\n\n");
} |
|
|
|
China
Post time: 2020-1-3 10:00:02
Author