数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究加权作业调度
我们得到不同工作的列表，同时还提供了这些工作的开始时间、结束时间和利润。我们的任务是找到一份工作子集，其中利润最大，并且没有工作相互重叠。
在此算法中，我们使用一个表来存储子问题的结果，并利用子问题的结果，可以自底向上地解决整个问题。
此算法的时间复杂度为 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
更新于： 17-6-2020
791 次浏览
广告