加权作业计划
列出了不同的工作，并提供了这些工作的开始时间，结束时间和利润。我们的任务是找到一部分工作，这些工作的利润最大，而且没有工作重叠。
在该算法中，我们使用一个表来存储子问题的结果，并使用子问题的结果，可以自下而上地解决整个问题。
该算法的时间复杂度为O（n^2），但是我们可以通过使用二进制搜索方法搜索冲突的作业将其更改为O（nLogn）。
输入输出
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