Giả sử chúng ta có một danh sách N công việc trong đó mỗi công việc có ba tham số. 1. Thời gian bắt đầu 2. Thời gian kết thúc 3. Lợi nhuận Chúng ta phải tìm một tập hợp con các công việc có liên quan đến lợi nhuận tối đa để không có hai công việc nào trong tập hợp con trùng nhau.
Vì vậy, nếu đầu vào là N =4 và J ={{2, 3, 55}, {4, 6, 25}, {7, 20, 150}, {3, 150, 250}}, thì đầu ra sẽ là [(2, 3, 55), (3, 150, 250)] và lợi nhuận tối ưu là 305
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm find_no_conflict (), hàm này sẽ lấy một mảng, chỉ mục,
-
left:=0, right:=index - 1
-
trong khi trái <=phải, thực hiện -
-
giữa:=(trái + phải) / 2
-
nếu công việc [giữa] .finish <=công việc [chỉ số]. bắt đầu, thì -
-
nếu công việc [giữa + 1] .finish <=công việc [chỉ mục]. bắt đầu, thì -
-
left:=mid + 1
-
-
trở về giữa
-
trở về giữa
-
-
-
Nếu không
-
right:=mid - 1
-
-
-
trả về -1
-
Từ phương thức chính, thực hiện như sau -
-
sắp xếp mảng job_list dựa trên thời gian hoàn thành
-
tạo một bảng cho các công việc được gọi là bảng có kích thước n
-
table [0] .value:=job_list [0] .profit
-
chèn job_list [0] vào cuối bảng [0]
-
để khởi tạo i:=1, khi i
-
include_profit:=job_list [i] .profit
-
l:=find_no_conflict (job_list, i)
-
nếu l không bằng - 1, thì -
-
include_profit:=include_profit + bảng [l] .value
-
-
nếu include_profit> table [i - 1] .value, thì -
-
table [i] .value:=include_profit
-
table [i] .job:=table [l] .job
-
chèn job_list [i] vào cuối bảng [i]
-
-
Nếu không
-
table [i]:=table [i - 1]
-
-
-
hiển thị công việc từ bảng
-
hiển thị Lợi nhuận tối ưu:=table [n - 1] .value
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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);
} Đầu vào
{{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}} Đầu ra
[(2, 3, 55),(3, 150, 250),] Optimal profit: 305