Lập kế hoạch công việc có trọng số

Danh sách các công việc khác nhau được đưa ra, với thời gian bắt đầu, thời gian kết thúc và lợi nhuận của công việc đó cũng được cung cấp cho các công việc đó. Nhiệm vụ của chúng tôi là tìm ra một nhóm nhỏ các công việc, nơi lợi nhuận là tối đa và không có công việc nào chồng chéo lên nhau.

Trong thuật toán này, chúng tôi sử dụng một bảng để lưu trữ kết quả của các bài toán con và sử dụng kết quả của các bài toán con, toàn bộ bài toán có thể được giải quyết theo cách từ dưới lên.

Độ phức tạp về thời gian của thuật toán này là O (n ^ 2), nhưng chúng ta có thể thay đổi nó thành O (n Log n) bằng cách sử dụng phương pháp tìm kiếm nhị phân để tìm kiếm các công việc mâu thuẫn nhau.

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

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.

Thuật toán

findMaxProfit(jobList, n)

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

Đầu ra: Lợi nhuận tối đa từ việc làm.

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

Ví dụ

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

Đầu ra

The maximum profit: 150