Vấn đề trình tự công việc với thời hạn

Trong bài toán này, có một danh sách các công việc được đưa ra. Trong danh sách, thời hạn và lợi nhuận cũng được đưa ra cho mỗi công việc. Mỗi công việc sẽ mất một đơn vị thời gian, vì vậy thời hạn tối thiểu cho một công việc là 1. Nếu chỉ có thể lên lịch một công việc tại một thời điểm thì hãy tối đa hóa lợi nhuận.

Để giải quyết vấn đề này, tất cả các tập con của tập hợp công việc được tạo ra để kiểm tra xem tập con riêng lẻ có khả thi hay không. Ngoài ra, hãy theo dõi lợi nhuận tối đa cho tất cả các tập hợp con khả thi đã tạo ra.

Độ phức tạp về thời gian của thuật toán này là O (n ^ 2)

Đầu vào và Đầu ra

Input:
A list of jobs with job id, deadline and profit. And the number of jobs n.
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
Output:
Following is maximum profit sequence of job sequence: c a e

Thuật toán

jobSequence(jobList, n)

Đầu vào - Danh sách công việc và số lượng công việc có trong danh sách.

Đầu ra - Trình tự, cách thức thực hiện các công việc.

Begin
   sort the jobs in jobList according to their profit create a list of job sequence and slot to track free time slots
   initially make all slots are free
   for all given jobs i do
      for all jobs in the list from ending of the list do
         if slot[j] is free then
            jobSequence[j] := i
            make slot[j] := fill
            break the loop
      done
   done

   for all slots when it is not free do
      print id of job using jobList[jobSequence[i]]
   done
End

Ví dụ

#include<iostream>
#include<algorithm>
using namespace std;

struct Job {
   char id;
   int deadLine;
   int profit;
};

bool comp(Job j1, Job j2) {
   return (j1.profit > j2.profit);    //compare jobs based on profit
}

int min(int a, int b) {
   return (a<b)?a:b;
}

void jobSequence(Job jobList[], int n) {
   sort(jobList, jobList+n, comp);    //sort jobList on profit

   int jobSeq[n];     // To store result (Sequence of jobs)
   bool slot[n];      // To keep track of free time slots

   for (int i=0; i<n; i++)
      slot[i] = false; //initially all slots are free

   for (int i=0; i<n; i++) {    //for all given jobs
      for (int j=min(n, jobList[i].deadLine)-1; j>=0; j--) {   //search from last free slot
         if (slot[j]==false) {
            jobSeq[j] = i;   // Add this job to job sequence
            slot[j] = true;  // mark this slot as occupied
            break;
         }
      }
   }

   for (int i=0; i<n; i++)
      if (slot[i])
         cout << jobList[jobSeq[i]].id << " ";    //display the sequence
}

int main() {
   Job jobList[] = {{'a',2,100}, {'b',1,19}, {'c',2,27},{'d',1,25},{'e',3,15}};
   int n = 5;
   cout << "Following is maximum profit sequence of job sequence: ";
   jobSequence(jobList, n);
}

Đầu ra

Following is maximum profit sequence of job sequence: c a e