Chọn chuỗi buổi không trùng giờ có tổng giá trị lớn nhất

1. Tạo phản ví dụ cho tham lam

Hai buổi A và B diễn ra [0,2), [2,4), mỗi buổi giá trị 3. Buổi C chiếm [0,4) và có giá trị 8. Chọn theo giờ kết thúc sớm nhất có thể chọn A rồi B, tổng 6. Nếu mục tiêu là tổng giá trị, phương án C tốt hơn. Việc đổi mục tiêu đã thay đổi tính đúng của chiến lược.

2. Xây công thức truy hồi

Sắp xếp buổi theo giờ kết thúc. Gọi p(i) là vị trí cuối của buổi kết thúc không muộn hơn lúc i bắt đầu. Bỏ i cho kết quả tốt nhất ở tiền tố trước. Chọn i cho giá trị của i cộng giá trị tốt nhất tới p(i). Hai trường hợp bao phủ mọi nghiệm tối ưu của tiền tố. Tìm p(i) bằng tìm kiếm nhị phân.

3. Truy vết để có danh sách buổi

Ví dụ thêm D [4,6) có giá trị 2. Phương án tối ưu là C và D, tổng 10. Khi truy ngược, nếu chọn i cho kết quả lớn hơn bỏ i, lưu mã i rồi nhảy về p(i). Khi bằng nhau, mẫu ưu tiên bỏ i để kết quả ổn định. Đổi quy ước phá hòa nếu cần số buổi hoặc tiêu chí phụ khác.

Chạy ví dụ bằng python gt_chon_buoi_co_trong_so.py.

from bisect import bisect_right

def chon_buoi(buoi):
    thu_tu = sorted(buoi, key=lambda x: (x[2], x[0]))
    cuoi = [b[2] for b in thu_tu]
    diem, tuong_thich = [0], []
    for i, (_, dau, _, gia_tri) in enumerate(thu_tu):
        p = bisect_right(cuoi, dau, 0, i)
        tuong_thich.append(p)
        diem.append(max(diem[-1], gia_tri + diem[p]))
    chon = []
    i = len(thu_tu)
    while i:
        if diem[i] > diem[i-1]:
            chon.append(thu_tu[i-1][0])
            i = tuong_thich[i-1]
        else:
            i -= 1
    return diem[-1], chon[::-1]

du_lieu = [("A", 0, 2, 3), ("B", 2, 4, 3), ("C", 0, 4, 8), ("D", 4, 6, 2)]
assert chon_buoi(du_lieu) == (10, ["C", "D"])
assert chon_buoi([]) == (0, [])
print(chon_buoi(du_lieu))

4. Kiểm tra giả định tài nguyên duy nhất

Truy hồi trên áp dụng khi chọn chuỗi cho một tài nguyên và các buổi có giá trị cộng được. Nếu nhiều phòng hoặc có ràng buộc giữa người tham dự ở các buổi, quan hệ tương thích không còn tóm gọn bởi một chỉ số p(i). Hãy đối chiếu với vét cạn trên dữ liệu nhỏ trước khi mở rộng mô hình.

Đọc thêm Tài liệu giải thuật của Princeton.