ปัญหาการจัดลำดับงานกับกำหนดเวลา

ในปัญหานี้ มีรายการงานให้ ในรายการ กำหนดเวลาและผลกำไรสำหรับแต่ละงานด้วย ทุกงานจะใช้เวลาหน่วยเดียว ดังนั้นกำหนดเวลาขั้นต่ำสำหรับงานคือ 1 หากกำหนดงานได้เพียงงานเดียวในแต่ละครั้ง ให้ทำกำไรสูงสุด

เพื่อแก้ปัญหานี้ เซ็ตย่อยของชุดงานทั้งหมดจะถูกสร้างขึ้นเพื่อตรวจสอบว่าแต่ละเซ็ตย่อยเป็นไปได้หรือไม่ นอกจากนี้ ติดตามผลกำไรสูงสุดสำหรับส่วนย่อยที่เป็นไปได้ทั้งหมดที่สร้างขึ้น

ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ O(n^2)

อินพุตและเอาต์พุต

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

อัลกอริทึม

jobSequence(jobList, n)

ป้อนข้อมูล - รายชื่องานและจำนวนงานที่อยู่ในรายการ

ผลลัพธ์ − ลำดับ วิธีการรับงาน

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

ตัวอย่าง

#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);
}

ผลลัพธ์

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