加权作业计划

列出了不同的工作，并提供了这些工作的开始时间，结束时间和利润。我们的任务是找到一部分工作，这些工作的利润最大，而且没有工作重叠。

在该算法中，我们使用一个表来存储子问题的结果，并使用子问题的结果，可以自下而上地解决整个问题。

该算法的时间复杂度为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++) {
      //查找包括当前工作在内的利润
      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