数据结构
网络
关系数据库管理系统
操作系统
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-06-2020
791 浏览量
广告