Lập Lịch Công Việc Có Trọng Số (Weighted Job Scheduling)

Giới thiệu

Cho danh sách công việc với thời gian bắt đầu, kết thúc và lợi nhuận. Chọn tập con công việc không chồng chéo nhau để tổng lợi nhuận tối đa.

Đầu vào và Đầu ra

Đầu vào: 4 công việc (start, end, profit): (3,5,25), (1,2,50), (6,15,75), (2,100,100)
Đầu ra: Lợi nhuận tối đa = 150 (chọn công việc 2 và 4, hoặc 2,1,3).

Thuật toán Quy hoạch động

Sắp xếp công việc theo thời gian kết thúc. Bảng table[i] = lợi nhuận tối đa xét đến công việc i. Với công việc i, tìm công việc j không xung đột gần nhất (j < i, end[j] ≤ start[i]). Lợi nhuận nếu chọn i = profit[i] + table[j]. So sánh với table[i-1].

findMaxProfit(jobList, n)
Begin
    sắp xếp jobList theo end tăng dần
    table[0] := jobList[0].profit
    for i := 1 to n-1 do
        addProfit := jobList[i].profit
        nonConflict := tìm j < i có end[j] <= start[i] (tìm ngược từ i-1)
        if nonConflict != -1 then addProfit += table[nonConflict]
        table[i] := max(addProfit, table[i-1])
    done
    return table[n-1]
End

Ví dụ C++

#include <iostream>
#include <algorithm>
using namespace std;

struct Job { int start, end, profit; };

bool comp(Job a, Job b) { return a.end < b.end; }

int nonConflictJob(Job jobs[], int i) {
    for (int j = i-1; j >= 0; j--)
        if (jobs[j].end <= jobs[i].start) return j;
    return -1;
}

int findMaxProfit(Job jobs[], int n) {
    sort(jobs, jobs+n, comp);
    int *table = new int[n];
    table[0] = jobs[0].profit;
    for (int i = 1; i < n; i++) {
        int addProfit = jobs[i].profit;
        int l = nonConflictJob(jobs, i);
        if (l != -1) addProfit += table[l];
        table[i] = max(addProfit, table[i-1]);
    }
    int result = table[n-1];
    delete[] table;
    return result;
}

int main() {
    Job jobs[] = {{3,5,25}, {1,2,50}, {6,15,75}, {2,100,100}};
    int n = 4;
    cout << "Lợi nhuận tối đa: " << findMaxProfit(jobs, n);
    return 0;
}

Kết quả

Lợi nhuận tối đa: 150