Đăng nhập để tham gia lộ trình luyện tập

LỘ TRÌNH THUẬT TOÁN THAM LAM

Thuật toán tham lam (Greedy) xây dựng lời giải bằng cách liên tiếp chọn một phương án tốt ở thời điểm hiện tại. Điểm khó không nằm ở việc sort, dùng Heap hay lấy phần tử lớn nhất, mà ở chỗ phải chứng minh rằng lựa chọn cục bộ đó không làm mất nghiệm tối ưu toàn cục.

Một lời giải Greedy thường có ba phần:

• xác định lựa chọn cục bộ;
• xác định bất biến (invariant) sau mỗi bước;
• chứng minh lựa chọn đó an toàn bằng đổi chỗ (exchange argument), đi trước (stays-ahead), ưu thế (dominance), quy nạp (induction) hoặc tính chất lát cắt (cut property).

Nếu không thể chỉ ra vì sao lựa chọn hiện tại luôn an toàn, cần nghi ngờ Greedy và thử tìm phản ví dụ nhỏ.

Giai đoạn 1 - NỀN TẢNG GREEDY: LOCAL CHOICE, DOMINANCE, PHẢN VÍ DỤ

Greedy cơ bản xuất hiện khi một lựa chọn cục bộ luôn không tệ hơn các lựa chọn khác.

Ví dụ, nếu mục tiêu là lấy được nhiều phần tử nhất dưới một ngân sách và mọi phần tử đóng góp như nhau, phần tử rẻ hơn có ưu thế hơn phần tử đắt hơn. Nếu đang chọn phần tử giá $b$ nhưng tồn tại phần tử giá $a$ với:

thì thay $b$ bằng $a$ không làm giảm số lượng phần tử được chọn và không làm tăng chi phí.

Đó là ý tưởng ưu thế (dominance).

Một khung chứng minh thường dùng là:

1. Lấy một nghiệm tối ưu bất kỳ.
2. Nếu nghiệm đó đã dùng lựa chọn Greedy thì giữ nguyên.
3. Nếu chưa dùng, thay một lựa chọn của nghiệm tối ưu bằng lựa chọn Greedy.
4. Chứng minh nghiệm vẫn hợp lệ và giá trị không xấu hơn.
5. Sau khi cố định bước đầu, bài toán còn lại có cùng dạng.

Mã giả tổng quát:

sắp xếp hoặc chuẩn bị dữ liệu theo tiêu chí đã chứng minh

khởi tạo trạng thái hiện tại

duyệt từng ứng viên:
    nếu ứng viên hiện tại là lựa chọn an toàn:
        chọn ứng viên
        cập nhật trạng thái

Greedy không đồng nghĩa với heuristic. Một heuristic chỉ “có vẻ hợp lý”, còn Greedy đúng phải có tính chất lựa chọn tham lam (greedy-choice property).

Một kỹ năng quan trọng là chủ động tạo phản ví dụ. Chẳng hạn với hệ tiền:

và cần đổi:

chiến lược lấy đồng lớn nhất trước cho:

dùng $3$ đồng, nhưng nghiệm tối ưu là:

chỉ dùng $2$ đồng. Vì vậy Greedy đổi tiền không đúng cho hệ tiền tổng quát.

Giai đoạn 2 - SORTING, EXCHANGE ARGUMENT, CUSTOM COMPARATOR

Rất nhiều bài Greedy thực chất là bài tìm một thứ tự xử lý tối ưu.

Ta xét hai phần tử $A$ và $B$ đứng cạnh nhau. So sánh hai thứ tự:

và:

Nếu chứng minh được thứ tự $A \rightarrow B$ không bao giờ tệ hơn, ta có thể dùng điều kiện đó làm comparator khi sắp xếp.

Đây là lập luận đổi chỗ (exchange argument).

Mã giả:

xây dựng comparator từ việc so sánh hai thứ tự A trước B và B trước A

sắp xếp toàn bộ phần tử theo comparator

xử lý theo thứ tự vừa sắp xếp

Một dạng thường gặp là so sánh tỉ lệ. Nếu điều kiện lý thuyết là:

không nên dùng số thực. So sánh bằng tích chéo:

Cần dùng kiểu số đủ lớn để tránh tràn.

Với bài ghép chuỗi để tạo chuỗi lớn nhất, thứ tự giữa hai chuỗi $a$ và $b$ thường được quyết định bởi:

Mã giả:

đổi mỗi phần tử thành chuỗi nếu cần

sắp xếp sao cho:
    a đứng trước b khi a + b lớn hơn b + a

ghép các chuỗi theo thứ tự đã sắp xếp

Comparator phải tạo ra thứ tự nhất quán. Không nên dùng điều kiện kiểu >= nếu nó phá tính chặt của phép so sánh.

Tie-break chỉ nên thêm khi đề yêu cầu hoặc khi đã chứng minh nó không ảnh hưởng tối ưu.

Giai đoạn 3 - GHÉP CẶP, HAI ĐẦU, MATCHING TUYẾN TÍNH

Sau khi sắp xếp, nhiều bài ghép cặp trở thành Greedy hai con trỏ.

Một mẫu rất quan trọng là xét phần tử lớn nhất còn lại.

Giả sử dãy đã tăng:

và hai phần tử có thể ghép nếu tổng không vượt $W$.

Ta xét phần tử lớn nhất $a_r$.

• Nếu $a_l+a_r\le W$, ghép $a_r$ với phần tử nhỏ nhất $a_l$.
• Nếu $a_l+a_r>W$, thì $a_r$ không thể ghép với bất kỳ phần tử nào khác, nên phải xử lý riêng.

Mã giả:

sắp xếp tăng

l = đầu dãy
r = cuối dãy

trong khi l <= r:
    nếu l == r:
        xử lý phần tử cuối cùng
        kết thúc

    nếu a[l] + a[r] thỏa điều kiện:
        ghép a[l] với a[r]
        tăng l
        giảm r
    ngược lại:
        xử lý a[r] riêng
        giảm r

Một mẫu khác là phần tử khả thi nhỏ nhất (smallest feasible).

Nếu mỗi yêu cầu cần một tài nguyên đủ lớn, nên ghép yêu cầu nhỏ nhất với tài nguyên nhỏ nhất vẫn đáp ứng được nó. Làm vậy giữ các tài nguyên lớn hơn cho các yêu cầu khó hơn phía sau.

Mã giả:

sắp xếp các yêu cầu tăng
sắp xếp các tài nguyên tăng

i = 0
j = 0

trong khi còn yêu cầu và tài nguyên:
    nếu tài nguyên j chưa đủ:
        tăng j
    ngược lại:
        ghép yêu cầu i với tài nguyên j
        tăng i
        tăng j

Không nên mặc định “ghép gần nhất” là đúng. Khoảng cách nhỏ cục bộ có thể làm mất một tài nguyên hiếm cần cho phần tử khác.

Giai đoạn 4 - INTERVAL SCHEDULING, DEADLINE, PHÂN TÀI NGUYÊN THEO THỜI GIAN

Với bài chọn nhiều đoạn không giao nhau nhất, Greedy chuẩn là:

Chọn đoạn kết thúc sớm nhất.

Nếu hai phương án cùng chọn một đoạn đầu tiên, đoạn kết thúc sớm hơn để lại nhiều không gian hơn cho phần còn lại.

Mã giả:

sắp xếp các đoạn theo thời điểm kết thúc tăng

last_end = thời điểm rất nhỏ
answer = 0

duyệt từng đoạn [l, r]:
    nếu l không nhỏ hơn last_end:
        chọn đoạn này
        last_end = r
        tăng answer

Độ phức tạp chủ yếu là:

do sắp xếp.

Không nên thay earliest finish bằng earliest start hoặc shortest interval nếu chưa có chứng minh.

Nếu mỗi interval có trọng số khác nhau và mục tiêu là tối đa tổng trọng số, bài thường chuyển sang DP thay vì Greedy thuần.

Với bài phân phòng hoặc tài nguyên cho các interval, thường cần Heap hoặc Multiset.

Nếu có nhiều tài nguyên tương đương, khi một interval mới bắt đầu, nên tái sử dụng tài nguyên vừa kết thúc phù hợp nhất.

Mã giả:

sắp xếp công việc theo thời điểm bắt đầu

tạo cấu trúc lưu thời điểm kết thúc của các tài nguyên

duyệt từng công việc:
    tìm tài nguyên đã kết thúc và phù hợp nhất

    nếu tìm được:
        tái sử dụng tài nguyên đó
    ngược lại:
        mở tài nguyên mới

    cập nhật thời điểm kết thúc mới

Trong bài deadline đơn vị thời gian, một chiến lược thường gặp là xếp công việc vào slot muộn nhất còn trống trước deadline để giữ các slot sớm cho công việc khác.

Nếu thời lượng công việc khác nhau và mục tiêu là tối đa số công việc hoàn thành, có thể dùng mẫu sort deadline + replace worst.

Giai đoạn 5 - INTERVAL COVERING, STABBING, SWEEP LINE

Cần phân biệt rõ hai bài toán:

• Interval Scheduling: chọn nhiều đoạn không giao nhau.
• Interval Covering: dùng ít đoạn nhất để phủ một miền.

Với bài phủ đoạn $[L,R]$, Greedy chuẩn là:

Tại điểm trái nhất chưa phủ, trong tất cả các đoạn bắt đầu không sau điểm đó, chọn đoạn vươn xa nhất về bên phải.

Mã giả:

sắp xếp interval theo đầu trái tăng

covered = L
i = 0

trong khi covered < R:
    farthest = covered
    best = không có

    trong khi i còn hợp lệ
    và interval[i].left <= covered:
        nếu interval[i].right > farthest:
            farthest = interval[i].right
            best = interval[i]

        tăng i

    nếu farthest == covered:
        kết luận không thể phủ

    chọn best
    covered = farthest

Bất biến là: sau cùng số interval đã chọn, Greedy luôn phủ xa nhất có thể.

Với bài đâm đoạn (interval stabbing), mục tiêu là chọn ít điểm nhất sao cho mỗi interval chứa ít nhất một điểm.

Chiến lược:

Sắp xếp theo đầu phải tăng. Khi gặp một interval chưa được điểm hiện tại phủ, đặt một điểm tại đầu phải của interval đó.

Mã giả:

sắp xếp interval theo đầu phải tăng

chưa có điểm được chọn

duyệt từng interval:
    nếu điểm hiện tại không nằm trong interval:
        chọn điểm tại đầu phải của interval

Nhiều bài hình học có thể biến đổi mỗi đối tượng thành một interval rồi áp dụng đúng hai mẫu trên.

Sweep Line chỉ là cách quét sự kiện. Quyết định chọn/xóa phần tử vẫn cần một invariant Greedy riêng.

Giai đoạn 6 - PRIORITY QUEUE, HUFFMAN, REPLACE-WORST, MARGINAL GAIN

Heap thường dùng khi “ứng viên tốt nhất hiện tại” thay đổi theo thời gian.

Optimal Merge và Huffman

Khi chi phí gộp hai phần tử là tổng của chúng và phần tử mới tiếp tục tham gia các lần gộp sau, luôn gộp hai phần tử nhỏ nhất.

Mã giả:

đưa mọi trọng số vào Min-Heap

answer = 0

trong khi Heap còn hơn một phần tử:
    lấy hai phần tử nhỏ nhất a và b

    c = a + b
    answer += c

    đưa c trở lại Heap

Độ phức tạp:

Không thể chỉ sort một lần, vì tổng mới sinh ra phải quay lại tập ứng viên.

Replace-Worst

Một mẫu rất quan trọng:

1. xử lý ứng viên theo một thứ tự đã chứng minh;
2. tạm nhận ứng viên;
3. nếu ràng buộc bị vi phạm, loại phần tử tệ nhất đang giữ.

Ví dụ với deadline và duration:

sắp xếp công việc theo deadline tăng

total_time = 0
tạo Max-Heap lưu duration đã chọn

duyệt từng công việc:
    nhận công việc
    total_time += duration
    đưa duration vào Heap

    nếu total_time vượt deadline hiện tại:
        bỏ duration lớn nhất trong Heap
        trừ duration đó khỏi total_time

Bất biến là: trên mỗi prefix deadline, ta giữ được số lượng công việc lớn nhất; trong số các tập có cùng số lượng, tổng thời gian đang dùng là nhỏ nhất có thể.

Retroactive Greedy

Đôi khi không nên quyết định ngay.

Ta trì hoãn lựa chọn đến khi bị bắt buộc, rồi chọn phương án tốt nhất trong toàn bộ lịch sử đã khả dụng.

Mã giả tổng quát:

tạo Heap chứa các lựa chọn đã đi qua nhưng chưa dùng

duyệt theo thời gian hoặc vị trí:
    thêm các lựa chọn mới vào Heap

    nếu trạng thái hiện tại không còn khả thi:
        nếu Heap rỗng:
            không có lời giải

        lấy lựa chọn tốt nhất trong Heap
        áp dụng nó để phục hồi tính khả thi

Marginal Gain

Nếu một đối tượng có thể được chọn nhiều lần và lợi ích biên thay đổi sau mỗi lần chọn, Heap phải lưu lợi ích hiện tại.

Sau khi chọn, cần tính lại key rồi đưa trở lại Heap.

Giai đoạn 7 - PHÂN BỔ TÀI NGUYÊN, EXTREME CHOICE, COVERAGE INVARIANT

Một Greedy điển hình của nhóm này là bất biến phủ (coverage invariant).

Giả sử sau khi xử lý một số phần tử, ta tạo được mọi tổng trong:

Nếu phần tử tiếp theo là $a$ và:

thì sau khi thêm $a$, ta tạo được mọi tổng trong:

Nếu:

thì $x+1$ là tổng nhỏ nhất không thể tạo.

Mã giả:

sắp xếp tăng

covered = 0

duyệt từng a:
    nếu a > covered + 1:
        dừng

    covered += a

đáp án là covered + 1

Chọn gap lớn nhất

Nếu có các điểm đã sắp xếp và cần dùng $K$ đoạn để phủ chúng, ban đầu một đoạn phủ toàn bộ có độ dài:

Mỗi lần cắt tại gap:

ta tiết kiệm đúng $g_i$.

Vì vậy chọn $K-1$ gap lớn nhất.

Mã giả:

sắp xếp các điểm

tính mọi gap giữa hai điểm liên tiếp

sắp xếp gap giảm dần

answer = toàn bộ span

trừ khỏi answer K-1 gap lớn nhất

Fractional Knapsack

Nếu tài nguyên có thể chia nhỏ, lấy theo giá trị trên một đơn vị giảm dần là đúng.

Nếu vật không thể chia, chiến lược theo tỉ lệ không đúng tổng quát. Khi đó thường phải dùng DP 0/1 Knapsack.

Bảo toàn tài nguyên linh hoạt

Nếu có hai loại tài nguyên và một loại dùng được trong nhiều tình huống hơn, thường nên giữ loại linh hoạt cho tương lai và tiêu loại ít linh hoạt khi cả hai đều dùng được.

Điều này chỉ đúng khi chứng minh được phép đổi tài nguyên ở hiện tại không làm giảm tập lựa chọn tương lai.

Giai đoạn 8 - CONSTRUCTIVE GREEDY I: INVARIANT, PARITY, PATTERN

Constructive Greedy không nhất thiết tối ưu một giá trị số. Mục tiêu là xây được một cấu hình hợp lệ.

Điểm quan trọng là bất biến có thể hoàn tất (completion invariant):

Sau mỗi bước, phần prefix đã xây vẫn có thể mở rộng thành một nghiệm đầy đủ.

Mã giả:

answer = rỗng

duyệt từng vị trí:
    xét các lựa chọn theo thứ tự Greedy

    chọn lựa chọn đầu tiên
    mà sau khi đặt vào
    phần còn lại vẫn còn khả năng hoàn tất

    nếu không có lựa chọn nào:
        kết luận không thể xây

Dùng parity

Nhiều construction chỉ phụ thuộc chẵn/lẻ.

Nếu hai phần tử được ghép khi có cùng parity, ta chia các chỉ số thành hai nhóm:

• chẵn;
• lẻ.

Sau đó chỉ ghép trong cùng nhóm, đồng thời xử lý số phần tử dư sao cho mỗi nhóm còn số lượng chẵn.

Pattern lặp

Nếu ràng buộc chỉ mang tính cục bộ, một mẫu chu kỳ ngắn đôi khi đủ:

Nhưng phải kiểm tra toàn bộ cửa sổ/ràng buộc, không chỉ vài vị trí đầu.

Minimal Disruption

Nếu bài yêu cầu sửa cấu hình càng ít càng tốt, thường giữ nguyên mọi phần đang hợp lệ và chỉ tác động vào các vị trí bắt buộc.

Giai đoạn 9 - CONSTRUCTIVE GREEDY II: REPAIR, RECONSTRUCTION, MULTISET

Ở mức cao hơn, ta có thể xây một cấu hình gần đúng rồi sửa các vi phạm cục bộ.

Đây là Greedy repair.

Repair bằng xoay vòng

Nếu một nhóm vị trí bị fixed point hoặc vi phạm cùng kiểu, có thể gom chúng lại rồi xoay các giá trị trong nhóm.

Mã giả:

xây lời giải tạm

thu thập các vị trí còn vi phạm

nếu số vị trí vi phạm đủ để xoay:
    xoay giá trị giữa các vị trí đó
ngược lại:
    xử lý trường hợp biên riêng

Multiset và complement

Nếu mỗi bước cần ghép phần tử lớn nhất với một complement xác định:

đưa mọi phần tử chưa dùng vào Multiset

trong khi Multiset chưa rỗng:
    lấy phần tử lớn nhất x

    tính phần tử cần ghép y

    nếu y không tồn tại:
        thất bại

    xóa đúng một lần xuất hiện của x
    xóa đúng một lần xuất hiện của y

    lưu cặp vào đáp án

Với duplicate, phải xóa đúng một occurrence.

Thử ít khả năng đầu

Có bài mà bước đầu chưa xác định duy nhất, nhưng sau khi cố định lựa chọn đầu tiên thì phần còn lại Greedy hoàn toàn.

Mã giả:

duyệt từng khả năng hợp lý cho bước đầu:
    sao chép trạng thái

    chạy Greedy cho phần còn lại

    nếu thành công:
        xuất đáp án
        kết thúc

Nếu có $O(n)$ khả năng đầu và mỗi lần xử lý $O(n\log n)$ thì tổng là:

Reconstruction

Khi sort làm mất vị trí ban đầu, lưu cả chỉ số:

mỗi phần tử lưu:
    giá trị
    vị trí gốc

Sau khi quyết định trên thứ tự đã sort, ghi kết quả trở lại vị trí gốc.

Giai đoạn 10 - GREEDY TRÊN CHUỖI/DÃY: LEXICOGRAPHIC, MONOTONIC DELETE, ORDERED SET

Xóa đơn điệu để tối ưu từ điển

Muốn xóa đúng $K$ chữ số để số còn lại nhỏ nhất, dùng cấu trúc giống Stack đơn điệu.

Khi gặp chữ số mới nhỏ hơn chữ số cuối đang giữ, nếu còn quyền xóa thì xóa chữ số lớn hơn ở trước.

Mã giả:

tạo dãy kết quả rỗng

duyệt từng chữ số d:
    trong khi còn quyền xóa
    và kết quả chưa rỗng
    và chữ số cuối lớn hơn d:

        xóa chữ số cuối
        giảm số lượt xóa

    thêm d vào cuối

nếu vẫn còn lượt xóa:
    xóa bớt từ cuối

Lý do: cải thiện ở vị trí sớm hơn luôn quan trọng hơn mọi cải thiện phía sau khi so sánh từ điển.

Muốn số lớn nhất thì đảo điều kiện so sánh.

Chọn subsequence theo thứ tự gốc

Nếu đề yêu cầu subsequence, không được sort toàn bộ dãy. Ta chỉ được chọn hoặc bỏ phần tử trong thứ tự ban đầu.

Ordered Set và Multiset

Khi mỗi bước cần phần tử lớn nhất không vượt ngưỡng $x$, dùng predecessor.

Mã giả:

it = phần tử đầu tiên lớn hơn x

nếu it đang ở đầu tập:
    không có phần tử phù hợp
ngược lại:
    lùi it một bước
    chọn phần tử tại it
    xóa nó khỏi tập nếu mỗi phần tử chỉ dùng một lần

Độ phức tạp mỗi truy vấn:

Patience-style Greedy

Với LIS, với mỗi độ dài $k$, ta chỉ cần giữ giá trị kết thúc nhỏ nhất có thể.

Một tail nhỏ hơn có ưu thế hơn tail lớn hơn vì cho nhiều khả năng nối dài hơn.

Mã giả:

tails = rỗng

duyệt từng x:
    tìm vị trí đầu tiên trong tails có giá trị >= x

    nếu không có:
        thêm x vào cuối tails
    ngược lại:
        thay vị trí đó bằng x

Độ phức tạp:

tails không nhất thiết là một LIS thực tế. Nếu cần truy vết, phải lưu thêm chỉ số và parent.

Giai đoạn 11 - GREEDY TOÁN HỌC, BIT, REDISTRIBUTION, ENUMERATION NHỎ

Median và khoảng cách $L_1$

Muốn tối thiểu:

thì một median của dãy là lựa chọn tối ưu.

Nếu các phần tử cuối cùng phải đứng liên tiếp, thường biến đổi:

rồi lấy median của $b_i$.

Mã giả:

thu thập vị trí pos của các phần tử cần gom

với mỗi vị trí thứ i:
    b[i] = pos[i] - i

lấy median của b

answer = tổng |b[i] - median|

Thử một số ít thứ tự cực trị

Nếu có hai thao tác cạnh tranh và không thể biết chắc thao tác nào nên làm trước, nhưng chỉ có vài thứ tự đáng xét, thử tất cả các thứ tự đó.

Ví dụ:

tính kết quả khi ưu tiên thao tác A trước B
tính kết quả khi ưu tiên thao tác B trước A

lấy kết quả tốt hơn

Đây là Greedy kết hợp enumeration nhỏ.

Quyết định bit từ cao xuống

Nếu cần tối ưu một số nhị phân dưới ràng buộc:

bit cao quan trọng hơn toàn bộ các bit thấp.

Ta thử quyết định từ bit cao nhất xuống. Chỉ chốt một bit nếu sau khi chốt vẫn tồn tại ít nhất một completion nằm trong miền hợp lệ.

Mã giả:

answer = 0

duyệt bit từ cao xuống:
    thử đặt bit theo hướng tốt cho objective

    nếu vẫn còn ít nhất một số hợp lệ trong [L, U]:
        giữ quyết định đó
    ngược lại:
        chọn giá trị bit còn lại

Redistribution

Khi cần cân bằng số phần tử giữa các lớp modulo, có thể chuyển surplus từ lớp này sang lớp kế tiếp.

Nếu mỗi lần tăng giá trị thêm $1$, residue thay đổi:

Greedy quét tuần tự các residue và chuyển phần dư tới nơi đang thiếu.

Công thức cực trị

Một số bài sau biến đổi cho ra trực tiếp một cận chặt.

Ví dụ nếu mỗi nhóm cần đúng $3$ đơn vị lấy từ hai loại tài nguyên $A,B$, số nhóm không thể vượt:

và cũng không thể vượt số lượng phía thiếu.

Nếu chứng minh được hai cận này đồng thời đạt được, có thể lấy min của các cận tương ứng.

Công thức đóng không tự động là Greedy; vẫn cần giải thích vì sao cách phân phối đạt được cận đó.

Giai đoạn 12 - HYBRID GREEDY: GRAPH, DSU/MST/DIJKSTRA, BINARY SEARCH FEASIBILITY, BOUNDARY

Giai đoạn cuối dùng Greedy như một thành phần trong lời giải lớn hơn.

Kruskal và tính chất lát cắt

Sắp xếp cạnh tăng theo trọng số.

Nếu hai đầu cạnh thuộc hai thành phần khác nhau, chọn cạnh đó.

Mã giả:

sắp xếp các cạnh theo trọng số tăng

khởi tạo DSU

duyệt từng cạnh (u, v, w):
    nếu u và v đang ở hai thành phần khác nhau:
        chọn cạnh
        gộp hai thành phần

Độ phức tạp:

Correctness đến từ tính chất lát cắt (cut property), không đến từ DSU.

DSU chỉ giúp kiểm tra nhanh cạnh có tạo chu trình hay không.

Dijkstra như một Greedy

Với trọng số cạnh không âm, khi đỉnh có khoảng cách tạm thời nhỏ nhất được lấy ra khỏi hàng đợi ưu tiên và trạng thái đó chưa lỗi thời, khoảng cách của nó đã được chốt.

Mã giả:

dist[source] = 0

đưa source vào Min-Heap

trong khi Heap chưa rỗng:
    lấy đỉnh u có dist nhỏ nhất

    nếu đây là bản ghi cũ:
        bỏ qua

    duyệt cạnh u -> v:
        nếu dist[u] + w < dist[v]:
            cập nhật dist[v]
            đưa trạng thái mới của v vào Heap

Độ phức tạp với adjacency list và Heap:

Nếu có cạnh âm, invariant chốt khoảng cách có thể bị phá.

Binary Search Answer + Greedy Check

Có những bài không phải Greedy thuần. Greedy chỉ được dùng để kiểm tra một đáp án giả định.

Giả sử ta có hàm:

và tính khả thi đơn điệu theo $X$.

Ví dụ chia mảng thành không quá $K$ đoạn liên tiếp, mỗi đoạn có tổng không vượt $X$.

Với $X$ cố định, chiến lược kiểm tra là nhồi mỗi đoạn dài nhất có thể.

Mã giả:

check(X):
    segments = 1
    current_sum = 0

    duyệt từng a:
        nếu a > X:
            trả false

        nếu current_sum + a <= X:
            current_sum += a
        ngược lại:
            segments += 1
            current_sum = a

    trả segments <= K

Giới hạn tìm kiếm tự nhiên:

Mã giả:

trong khi lo < hi:
    mid = (lo + hi) / 2

    nếu check(mid) đúng:
        hi = mid
    ngược lại:
        lo = mid + 1

đáp án = lo

Ở dạng này cần hai chứng minh riêng:

• Greedy trong check(X) là đúng;
• tính khả thi theo $X$ là đơn điệu.

Ranh giới của Greedy

Khi lựa chọn cục bộ không chứng minh được an toàn, cần chuyển mô hình.

Các ranh giới thường gặp:

• weighted interval scheduling chuyển sang DP;
• 0/1 knapsack chuyển sang DP;
• cạnh âm phá Dijkstra;
• matching tổng quát không thể thay bằng ghép cặp cục bộ đơn giản;
• bài tối ưu ngưỡng đơn điệu thường là Binary Search Answer chứ không phải Greedy thuần.

Năng lực quan trọng nhất ở giai đoạn này là nhận ra Greedy nằm ở đâu trong lời giải và khi nào phải dùng một thuật toán khác.