Tìm các công việc trong Lập lịch công việc có trọng số trong C++

Cho danh sách N công việc, mỗi công việc có 3 tham số: 1. Thời gian bắt đầu 2. Thời gian kết thúc 3. Lợi nhuận. Tìm tập con công việc có lợi nhuận tối đa sao cho không có hai công việc nào chồng chéo.

Ví dụ: N = 4, J = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}, kết quả là [(2, 3, 55),(3, 150, 250)] và lợi nhuận tối ưu 305.

Các bước giải quyết:

• Định nghĩa hàm find_no_conflict(jobs, index)
• left = 0, right = index - 1
• Trong khi left <= right: mid = (left + right) / 2; nếu jobs[mid].finish <= jobs[index].start thì kiểm tra jobs[mid+1].finish <= jobs[index].start để điều chỉnh left hoặc trả về mid; ngược lại right = mid - 1
• Trả về -1
• Từ main: sắp xếp mảng job_list theo finish time; tạo bảng table kích thước n; table[0].value = job_list[0].profit; thêm job_list[0] vào table[0]; với i từ 1 đến n-1: include_profit = job_list[i].profit; l = find_no_conflict(job_list, i); nếu l != -1 thì include_profit += table[l].value; nếu include_profit > table[i-1].value thì table[i].value = include_profit, table[i].job = table[l].job, thêm job_list[i]; ngược lại table[i] = table[i-1]; in công việc từ table và lợi nhuận tối ưu.

Ví dụ (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);
}

Đầ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