資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢 C++ 中加權作業排程相關的職位
假設我們有一個包含 N 個作業的列表，每個作業有三個引數：1. 開始時間 2. 結束時間 3. 利潤。我們需要找到一個與最大利潤相關的作業子集，使得子集中沒有兩個作業重疊。
因此，如果輸入類似於 N = 4 且 J = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}，則輸出將為 [(2, 3, 55),(3, 150, 250)]，最優利潤為 305。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 find_no_conflict()，它將接收一個作業陣列 jobs 和索引 index 作為輸入。
left := 0, right := index - 1
當 left <= right 時，執行以下操作：
mid := (left + right) / 2
如果 jobs[mid].finish <= jobs[index].start，則執行以下操作：
如果 jobs[mid + 1].finish <= jobs[index].start，則執行以下操作：
left := mid + 1
返回 mid
返回 mid
否則
right := mid - 1
返回 -1
在主方法中，執行以下操作：
根據結束時間對陣列 job_list 進行排序。
建立一個名為 table 的作業表，大小為 n。
table[0].value := job_list[0].profit
將 job_list[0] 插入到 table[0] 的末尾。
從 i := 1 開始，當 i < n 時，更新 i（增加 1），執行以下操作：
include_profit := job_list[i].profit
l := find_no_conflict(job_list, i)
如果 l 不等於 -1，則執行以下操作：
include_profit := include_profit + table[l].value
如果 include_profit > table[i - 1].value，則執行以下操作：
table[i].value := include_profit
table[i].job := table[l].job
將 job_list[i] 插入到 table[i] 的末尾。
否則
table[i] := table[i - 1]
顯示 table 中的作業。
顯示最優利潤 := table[n - 1].value
示例（C++）
讓我們看看以下實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Job {
public:
int start, finish, profit;
};
struct job_with_weight {
vector<Job> job;
int value;
};
bool jobComparator(Job s1, Job s2) {
return (s1.finish < s2.finish);
}
int find_no_conflict(Job jobs[], int index) {
int left = 0, right = index - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (jobs[mid].finish <= jobs[index].start) {
if (jobs[mid + 1].finish <= jobs[index].start)
left = mid + 1;
else
return mid;
}
else
right = mid - 1;
}
return -1;
}
int get_max_profit(Job job_list[], int n) {
sort(job_list, job_list + n, jobComparator);
job_with_weight table[n];
table[0].value = job_list[0].profit;
table[0].job.push_back(job_list[0]);
for (int i = 1; i < n; i++) {
int include_profit = job_list[i].profit;
int l = find_no_conflict(job_list, i);
if (l != - 1)
include_profit += table[l].value;
if (include_profit > table[i - 1].value){
table[i].value = include_profit;
table[i].job = table[l].job;
table[i].job.push_back(job_list[i]);
}
else
table[i] = table[i - 1];
}
cout << "[";
for (int i=0; i<table[n-1].job.size(); i++) {
Job j = table[n-1].job[i];
cout << "(" << j.start << ", " << j.finish << ", " << j.profit << "),";
}
cout << "]\nOptimal profit: " << table[n - 1].value;
}
int main() {
Job arr[] = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}};
int n = sizeof(arr)/sizeof(arr[0]);
get_max_profit(arr, n);
}輸入
{{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}輸出
[(2, 3, 55),(3, 150, 250),] Optimal profit: 305
177 次檢視
