資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告