기한이 있는 작업 순서 문제

이 문제에는 주어진 작업 목록이 있습니다. 목록에는 각 작업에 대한 마감일과 수익도 나와 있습니다. 모든 작업에는 단일 시간 단위가 소요되므로 작업의 최소 기한은 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