가중 작업 스케줄링

다양한 작업 목록이 제공되며, 시작 시간, 종료 시간 및 해당 작업의 수익도 해당 작업에 대해 제공됩니다. 우리의 임무는 이익이 최대이고 서로 겹치는 작업이 없는 작업의 하위 집합을 찾는 것입니다.

이 알고리즘에서는 테이블을 사용하여 하위 문제의 결과를 저장하고 하위 문제의 결과를 사용하여 전체 문제를 상향식 방식으로 해결할 수 있습니다.

이 알고리즘의 시간 복잡도는 O(n^2)이지만 충돌하는 작업을 검색하기 위해 이진 검색 방법을 사용하여 O(n Log n)으로 변경할 수 있습니다.

입력 및 출력

Input:
The start time, finish time and profit of some jobs as matrix form. And number of jobs. Here 4 jobs are present.
3   5  25
1   2  50
6  15  75
2 100 100

Output:
The maximum profit 150.
The job sequence is job 2, job 4, or job 2, job 1, job 3. for both cases the max profit is 150 here.

알고리즘

findMaxProfit(jobList, n)

입력: 작업 목록 및 작업 수입니다.

출력: 작업의 최대 이익.

Begin
   sort job list according to their ending time
   define table to store results
   table[0] := jobList[0].profit

   for i := 1 to n-1, do
      addProfit := jobList[i].profit
      nonConflict := find jobs which is not conflicting with others
      if any non-conflicting job found, then
         addProfit := addProfit + table[nonConflict]
      if addProfit > table[i - 1], then
         table[i] := addProfit
      else
         table[i] := table[i-1]
   done
   result := table[n-1]
   return result
End

예

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

struct Job {
   int start, end, profit;
};

bool comp(Job job1, Job job2) {
   return (job1.end < job2.end);
}

int nonConflictJob(Job jobList[], int i) {       //non conflicting job of jobList[i]
   for (int j=i-1; j>=0; j--) {
      if (jobList[j].end <= jobList[i-1].start)
         return j;
   }
   return -1;
}

int findMaxProfit(Job jobList[], int n) {
   sort(jobList, jobList+n, comp);           //sort jobs based on the ending time

   int *table = new int[n];       //create jon table
   table[0] = jobList[0].profit;

   for (int i=1; i<n; i++) {
      // Find profit including the current job
      int addProfit = jobList[i].profit;
      int l = nonConflictJob(jobList, i);
      if (l != -1)
         addProfit += table[l];
      table[i] = (addProfit>table[i-1])?addProfit:table[i-1];       //find maximum
   }

   int result = table[n-1];
   delete[] table;                 //clear table from memory
   return result;
}

int main() {
   Job jobList[] = {
      {3, 5, 25},
      {1, 2, 50},
      {6, 15, 75},
      {2, 100, 100}
   };

   int n = 4;
   cout << "The maximum profit: " << findMaxProfit(jobList, n);
   return 0;
}

출력

The maximum profit: 150