Bài học

Nguyên lý tham lam và lập luận đổi chỗ

Mục tiêu bài học

Sau bài này, em nhận ra khi nào một chiến lược tham lam — chọn quyết định tốt nhất tại từng bước, không quay lại sửa — chắc chắn cho lời giải tối ưu, và biết chứng minh điều đó bằng lập luận đổi chỗ (exchange argument) thay vì tin theo trực giác hay vài ví dụ thử tay. Quan trọng không kém: em sẽ thấy nhiều bài toán trông giống tham lam nhưng tham lam lại cho kết quả sai — nhận ra đúng ranh giới này là kỹ năng giá trị nhất của cả cụm chuyên đề tham lam ở kỳ thi HSG.

Sau bài này, em nhận ra khi nào một chiến lược tham lam — chọn quyết định tốt nhất tại từng bước, không quay lại sửa — chắc chắn cho lời giải tối ưu, và biết chứng minh điều đó bằng **lập luận đổi chỗ** (exchange argument) thay vì tin theo trực giác hay vài ví dụ thử tay. Quan trọng không kém: em sẽ thấy nhiều bài toán trông giống tham lam nhưng tham lam lại cho kết quả sai — nhận ra đúng ranh giới này là kỹ năng giá trị nhất của cả cụm chuyên đề tham lam ở kỳ thi HSG.

Cần nhớ trước

Em cần nhớ: sắp xếp một danh sách theo một hàm so sánh tuỳ chọn bằng sorted(key=...) hoặc functools.cmp_to_key, độ phức tạp $O(n\log n)$ của thuật toán sắp xếp, và cách viết hàm đệ quy cơ bản đã học ở Tin học 10.

Em cần nhớ: sắp xếp một danh sách theo một hàm so sánh tuỳ chọn bằng `sorted(key=...)` hoặc `functools.cmp_to_key`, độ phức tạp $O(n\log n)$ của thuật toán sắp xếp, và cách viết hàm đệ quy cơ bản đã học ở Tin học 10.

So với mức chuẩn: đề chuẩn lớp 11 thường cho sẵn chiến lược tham lam rồi yêu cầu em cài đặt — ví dụ 'sắp xếp mảng tăng dần rồi duyệt'. Đề HSG đảo ngược: em phải tự tìm ra tiêu chí sắp xếp đúng, rồi chứng minh nó đúng bằng lập luận, không được đoán rồi thử vài ví dụ nhỏ. Một tiêu chí đúng trên ba ví dụ đầu vẫn có thể sai ở ví dụ thứ tư — chỉ có chứng minh mới đảm bảo đúng với mọi đầu vào.

**So với mức chuẩn:** đề chuẩn lớp 11 thường cho sẵn chiến lược tham lam rồi yêu cầu em cài đặt — ví dụ 'sắp xếp mảng tăng dần rồi duyệt'. Đề HSG đảo ngược: em phải tự tìm ra tiêu chí sắp xếp đúng, rồi **chứng minh** nó đúng bằng lập luận, không được đoán rồi thử vài ví dụ nhỏ. Một tiêu chí đúng trên ba ví dụ đầu vẫn có thể sai ở ví dụ thứ tư — chỉ có chứng minh mới đảm bảo đúng với mọi đầu vào.

Nguyên lý tham lam: tốt nhất tại mỗi bước, không quay lại

Một thuật toán tham lam xây dựng lời giải theo từng bước, và ở mỗi bước chọn phương án tốt nhất hiện có mà không bao giờ xét lại các bước trước. Chiến lược này chỉ cho lời giải tối ưu khi bài toán có hai tính chất: tính chất lựa chọn tham lam (greedy choice property) — luôn tồn tại một lời giải tối ưu bắt đầu bằng đúng lựa chọn tham lam; và cấu trúc con tối ưu (optimal substructure) — sau khi chọn xong bước đầu, phần bài toán còn lại cũng giải tối ưu được bằng chính chiến lược đó. Thiếu một trong hai, tham lam có thể đưa ra một lời giải nghe hợp lý nhưng sai.

Một thuật toán tham lam xây dựng lời giải theo từng bước, và ở mỗi bước chọn phương án tốt nhất hiện có mà không bao giờ xét lại các bước trước. Chiến lược này chỉ cho lời giải **tối ưu** khi bài toán có hai tính chất: **tính chất lựa chọn tham lam** (greedy choice property) — luôn tồn tại một lời giải tối ưu bắt đầu bằng đúng lựa chọn tham lam; và **cấu trúc con tối ưu** (optimal substructure) — sau khi chọn xong bước đầu, phần bài toán còn lại cũng giải tối ưu được bằng chính chiến lược đó. Thiếu một trong hai, tham lam có thể đưa ra một lời giải nghe hợp lý nhưng sai.

Kỹ thuật chứng minh: lập luận đổi chỗ

Lập luận đổi chỗ chứng minh một tiêu chí sắp xếp tham lam là tối ưu theo bốn bước: giả sử tồn tại một lời giải tối ưu không theo đúng thứ tự tham lam; trong lời giải đó, tìm hai phần tử liền kề bị đảo ngược so với tiêu chí; đổi chỗ hai phần tử liền kề này và so sánh — chứng minh lời giải sau khi đổi chỗ không tệ hơn; lặp lại cho đến khi thứ tự trùng với tham lam, từ đó kết luận thứ tự tham lam cũng tối ưu. Điểm mấu chốt: chỉ cần xét đổi chỗ hai phần tử liền kề — không cần duyệt qua mọi hoán vị, vì mọi hoán vị đều đưa được về thứ tự đích bằng một dãy các phép đổi chỗ liền kề.

Lập luận đổi chỗ chứng minh một tiêu chí sắp xếp tham lam là tối ưu theo bốn bước: giả sử tồn tại một lời giải tối ưu **không** theo đúng thứ tự tham lam; trong lời giải đó, tìm hai phần tử **liền kề** bị đảo ngược so với tiêu chí; đổi chỗ hai phần tử liền kề này và so sánh — chứng minh lời giải sau khi đổi chỗ không tệ hơn; lặp lại cho đến khi thứ tự trùng với tham lam, từ đó kết luận thứ tự tham lam cũng tối ưu. Điểm mấu chốt: chỉ cần xét đổi chỗ hai phần tử **liền kề** — không cần duyệt qua mọi hoán vị, vì mọi hoán vị đều đưa được về thứ tự đích bằng một dãy các phép đổi chỗ liền kề.

Khuôn chứng minh này áp dụng cho cả hai ví dụ dưới đây — chỉ khác nhau ở tiêu chí so sánh và đại lượng cần so sánh sau khi đổi chỗ.

Ví dụ mở đầu — ghép số lớn nhất

Cho bốn số 34, 349, 3, 3492. Ghép cả bốn số này (giữ nguyên từng số, chỉ đổi thứ tự) thành một chuỗi số lớn nhất có thể. So sánh trực tiếp từng cặp số theo giá trị không đủ: 349 < 3492 xét theo giá trị số học, nhưng thử ghép '349' trước '3492' cho '3493492', còn ghép ngược lại cho '3492349' — hai kết quả khác nhau và thứ tự theo giá trị số học không quyết định thứ tự ghép đúng. Cần một tiêu chí so sánh khác, tính trên cặp chuỗi ký tự chứ không phải trên giá trị số.

Cho bốn số 34, 349, 3, 3492. Ghép cả bốn số này (giữ nguyên từng số, chỉ đổi thứ tự) thành một chuỗi số lớn nhất có thể. So sánh trực tiếp từng cặp số theo giá trị không đủ: 349 < 3492 xét theo giá trị số học, nhưng thử ghép '349' trước '3492' cho '3493492', còn ghép ngược lại cho '3492349' — hai kết quả khác nhau và **thứ tự theo giá trị số học không quyết định thứ tự ghép đúng**. Cần một tiêu chí so sánh khác, tính trên cặp chuỗi ký tự chứ không phải trên giá trị số.

Ví dụ

Ví dụ 1 — Ghép các số thành số lớn nhất

1
Xếp số $a$ đứng trước số $b$ khi và chỉ khi chuỗi nối $a\!+\!b$ (ghép trực tiếp hai chuỗi ký tự) lớn hơn chuỗi nối $b\!+\!a$ , so sánh theo thứ tự từ điển (vì hai chuỗi nối luôn cùng độ dài). Đây là bài toán sắp xếp với một comparator tuỳ chỉnh, không phải so sánh giá trị số trực tiếp.
Xếp số $a$ đứng trước số $b$ khi và chỉ khi chuỗi nối $a\!+\!b$ (ghép trực tiếp hai chuỗi ký tự) lớn hơn chuỗi nối $b\!+\!a$, so sánh theo thứ tự từ điển (vì hai chuỗi nối luôn cùng độ dài). Đây là bài toán sắp xếp với một **comparator** tuỳ chỉnh, không phải so sánh giá trị số trực tiếp.

from functools import cmp_to_key

def largest_number(nums):
    strs = [str(x) for x in nums]
    def cmp(a, b):
        if a + b > b + a:
            return -1   # a dung truoc b
        if a + b < b + a:
            return 1
        return 0
    strs.sort(key=cmp_to_key(cmp))
    return "".join(strs)

3
Với nums = [34, 349, 3, 3492], hàm trên trả về "3493492343". Đối chiếu bằng cách duyệt toàn bộ $4! = 24$ cách sắp xếp và lấy số lớn nhất (brute force): kết quả cũng là 3493492343 — khớp. Với $n$ số, duyệt toàn bộ hoán vị có độ phức tạp $O(n!)$ , không khả thi khi $n$ lớn; sắp xếp bằng comparator chỉ tốn $O(n\log n \cdot L)$ với $L$ là độ dài chuỗi lớn nhất.
Với `nums = [34, 349, 3, 3492]`, hàm trên trả về `"3493492343"`. Đối chiếu bằng cách duyệt toàn bộ $4! = 24$ cách sắp xếp và lấy số lớn nhất (brute force): kết quả cũng là **3493492343** — khớp. Với $n$ số, duyệt toàn bộ hoán vị có độ phức tạp $O(n!)$, không khả thi khi $n$ lớn; sắp xếp bằng comparator chỉ tốn $O(n\log n \cdot L)$ với $L$ là độ dài chuỗi lớn nhất.
4
Giả sử một cách ghép tối ưu có hai số $a, b$ đứng liền kề theo thứ tự $a$ trước $b$ , nhưng $a+b < b+a$ (vi phạm tiêu chí). Gọi $X$ là chuỗi các số đứng trước cặp này, $Y$ là chuỗi các số đứng sau. Giá trị toàn bộ khi giữ nguyên thứ tự là $X \cdot a \cdot b \cdot Y$ , khi đổi chỗ $a, b$ là $X \cdot b \cdot a \cdot Y$ . Vì $X$ và $Y$ không đổi, việc so sánh hai cách ghép quy về đúng so sánh $a+b$ với $b+a$ — mà theo giả thiết $a+b < b+a$ , nên đổi chỗ làm tăng giá trị chuỗi ghép, mâu thuẫn với việc cách ban đầu đã tối ưu. Vậy trong mọi cách ghép tối ưu, không có cặp liền kề nào vi phạm tiêu chí — nghĩa là thứ tự do comparator tạo ra chính là tối ưu.
Giả sử một cách ghép tối ưu có hai số $a, b$ đứng liền kề theo thứ tự $a$ trước $b$, nhưng $a+b < b+a$ (vi phạm tiêu chí). Gọi $X$ là chuỗi các số đứng trước cặp này, $Y$ là chuỗi các số đứng sau. Giá trị toàn bộ khi giữ nguyên thứ tự là $X \cdot a \cdot b \cdot Y$, khi đổi chỗ $a, b$ là $X \cdot b \cdot a \cdot Y$. Vì $X$ và $Y$ không đổi, việc so sánh hai cách ghép quy về đúng so sánh $a+b$ với $b+a$ — mà theo giả thiết $a+b < b+a$, nên đổi chỗ **làm tăng** giá trị chuỗi ghép, mâu thuẫn với việc cách ban đầu đã tối ưu. Vậy trong mọi cách ghép tối ưu, không có cặp liền kề nào vi phạm tiêu chí — nghĩa là thứ tự do comparator tạo ra chính là tối ưu.
5
Mẫu chung: bất cứ bài 'ghép chuỗi để tối ưu giá trị' nào cũng thử tiêu chí so sánh cặp $a+b$ với $b+a$ trước tiên. Biến thể: muốn số nhỏ nhất thay vì lớn nhất thì đảo dấu so sánh — nhưng cần xử lý riêng trường hợp có số 0 ở đầu (ví dụ ghép 0, 0, 1 nên cho '001' hay '100'? Đề bài cụ thể sẽ quy định có bỏ số 0 thừa ở đầu hay không).
**Mẫu chung:** bất cứ bài 'ghép chuỗi để tối ưu giá trị' nào cũng thử tiêu chí so sánh cặp $a+b$ với $b+a$ trước tiên. Biến thể: muốn số **nhỏ nhất** thay vì lớn nhất thì đảo dấu so sánh — nhưng cần xử lý riêng trường hợp có số 0 ở đầu (ví dụ ghép 0, 0, 1 nên cho '001' hay '100'? Đề bài cụ thể sẽ quy định có bỏ số 0 thừa ở đầu hay không).
6
Ta có bốn số 34, 349, 3, 3492. Xét tiêu chí sắp xếp: số $a$ đứng trước $b$ khi $a+b > b+a$ (so sánh chuỗi). Áp dụng lần lượt: '3492' đứng trước '349' vì '3492349' > '3493492' — sai, kiểm tra lại bằng cài đặt ở trên ta có kết quả đúng là ghép theo thứ tự comparator cho chuỗi 3493492343. Theo lập luận đổi chỗ đã chứng minh, không cặp liền kề nào trong thứ tự này vi phạm tiêu chí, nên đây là thứ tự tối ưu. Vậy số lớn nhất ghép được là $3493492343$ .
Ta có bốn số 34, 349, 3, 3492. Xét tiêu chí sắp xếp: số $a$ đứng trước $b$ khi $a+b > b+a$ (so sánh chuỗi). Áp dụng lần lượt: '3492' đứng trước '349' vì '3492349' > '3493492' — sai, kiểm tra lại bằng cài đặt ở trên ta có kết quả đúng là ghép theo thứ tự comparator cho chuỗi **3493492343**. Theo lập luận đổi chỗ đã chứng minh, không cặp liền kề nào trong thứ tự này vi phạm tiêu chí, nên đây là thứ tự tối ưu. Vậy số lớn nhất ghép được là $3493492343$.

Ví dụ 2 — Lịch một máy để độ trễ lớn nhất nhỏ nhất

Bài toán tiếp theo có dạng khác hẳn: không ghép chuỗi mà lập lịch. Cho $n$ công việc trên một máy đơn, xử lý tuần tự không ngắt quãng, mỗi công việc $i$ có thời gian xử lý $p_i$ và thời hạn $d_i$ . Với một thứ tự xử lý, gọi $C_i$ là thời điểm hoàn thành công việc $i$ và độ trễ của nó là $C_i - d_i$ (âm nghĩa là xong sớm). Mục tiêu: chọn thứ tự sao cho độ trễ lớn nhất $L_{\max} = \max_i (C_i - d_i)$ là nhỏ nhất.

Bài toán tiếp theo có dạng khác hẳn: không ghép chuỗi mà **lập lịch**. Cho $n$ công việc trên một máy đơn, xử lý tuần tự không ngắt quãng, mỗi công việc $i$ có thời gian xử lý $p_i$ và thời hạn $d_i$. Với một thứ tự xử lý, gọi $C_i$ là thời điểm hoàn thành công việc $i$ và **độ trễ** của nó là $C_i - d_i$ (âm nghĩa là xong sớm). Mục tiêu: chọn thứ tự sao cho **độ trễ lớn nhất** $L_{\max} = \max_i (C_i - d_i)$ là nhỏ nhất.

Ví dụ

Ví dụ 2 — Tối thiểu hoá độ trễ lớn nhất

1
Xử lý công việc theo thời hạn tăng dần (Earliest Deadline First — EDD): công việc có hạn gần nhất được làm trước. Trực giác: để công việc có hạn gấp trễ nhất có thể là lãng phí, nên ưu tiên hạn gấp trước.

def min_lmax_edd(jobs):  # jobs: list cua (p, d)
    order = sorted(jobs, key=lambda job: job[1])  # theo han tang dan
    t = 0
    lmax = float("-inf")
    for p, d in order:
        t += p
        lmax = max(lmax, t - d)
    return lmax, order

3
Với jobs = [(4,4), (2,5), (5,12), (3,9)] (thời gian xử lý, thời hạn), EDD cho thứ tự [(4, 4), (2, 5), (3, 9), (5, 12)], thời điểm hoàn thành lần lượt 4, 6, 9, 14 và $L_{\max} = 2$ . Đối chiếu bằng duyệt toàn bộ $4! = 24$ thứ tự: giá trị nhỏ nhất cũng là 2 — khớp. Thử một thứ tự 'trông hợp lý' khác — ưu tiên việc lâu nhất trước — cho $L_{\max} = 9$ , tệ hơn hẳn.
Với `jobs = [(4,4), (2,5), (5,12), (3,9)]` (thời gian xử lý, thời hạn), EDD cho thứ tự `[(4, 4), (2, 5), (3, 9), (5, 12)]`, thời điểm hoàn thành lần lượt 4, 6, 9, 14 và $L_{\max} = 2$. Đối chiếu bằng duyệt toàn bộ $4! = 24$ thứ tự: giá trị nhỏ nhất cũng là **2** — khớp. Thử một thứ tự 'trông hợp lý' khác — ưu tiên việc **lâu nhất trước** — cho $L_{\max} = 9$, tệ hơn hẳn.
4
Xét một thứ tự tối ưu có hai công việc $i, j$ liền kề, $i$ chạy trước $j$ , nhưng $d_i > d_j$ (vi phạm EDD). Gọi $t$ là thời điểm bắt đầu khối $\{i,j\}$ trong lịch. Trước khi đổi chỗ: $i$ hoàn thành lúc $t+p_i$ (trễ $t+p_i-d_i$ ), $j$ hoàn thành lúc $t+p_i+p_j$ (trễ $t+p_i+p_j-d_j$ ). Sau khi đổi chỗ (đưa $j$ chạy trước): $j$ hoàn thành lúc $t+p_j$ (trễ $t+p_j-d_j$ ), $i$ hoàn thành lúc $t+p_i+p_j$ (trễ $t+p_i+p_j-d_i$ ). Thời điểm hoàn thành công việc cuối cùng của khối vẫn là $t+p_i+p_j$ ở cả hai thứ tự, nên mọi công việc khác không đổi. So sánh độ trễ lớn nhất trong khối: vì $d_i > d_j$ , có thể chứng minh $\max(t+p_j-d_j,\, t+p_i+p_j-d_i) \le \max(t+p_i-d_i,\, t+p_i+p_j-d_j)$ — đổi chỗ không làm tăng độ trễ lớn nhất của khối. Do đó $L_{\max}$ toàn cục không tăng, và lặp lại bước đổi chỗ đến khi hết vi phạm sẽ đưa về đúng thứ tự EDD mà không làm lời giải tệ hơn — vậy EDD tối ưu.
Xét một thứ tự tối ưu có hai công việc $i, j$ liền kề, $i$ chạy trước $j$, nhưng $d_i > d_j$ (vi phạm EDD). Gọi $t$ là thời điểm bắt đầu khối $\{i,j\}$ trong lịch. Trước khi đổi chỗ: $i$ hoàn thành lúc $t+p_i$ (trễ $t+p_i-d_i$), $j$ hoàn thành lúc $t+p_i+p_j$ (trễ $t+p_i+p_j-d_j$). Sau khi đổi chỗ (đưa $j$ chạy trước): $j$ hoàn thành lúc $t+p_j$ (trễ $t+p_j-d_j$), $i$ hoàn thành lúc $t+p_i+p_j$ (trễ $t+p_i+p_j-d_i$). Thời điểm hoàn thành công việc cuối cùng của khối vẫn là $t+p_i+p_j$ ở cả hai thứ tự, nên mọi công việc khác không đổi. So sánh độ trễ lớn nhất trong khối: vì $d_i > d_j$, có thể chứng minh $\max(t+p_j-d_j,\, t+p_i+p_j-d_i) \le \max(t+p_i-d_i,\, t+p_i+p_j-d_j)$ — đổi chỗ không làm tăng độ trễ lớn nhất của khối. Do đó $L_{\max}$ toàn cục không tăng, và lặp lại bước đổi chỗ đến khi hết vi phạm sẽ đưa về đúng thứ tự EDD mà không làm lời giải tệ hơn — vậy EDD tối ưu.
5
Kết quả này chỉ đúng cho mục tiêu $L_{\max}$ . Với một mục tiêu nghe rất giống — số lượng công việc trễ — EDD thuần không còn tối ưu; xem mục Bẫy thường gặp ngay sau đây. Đây chính là điểm học sinh hay nhầm nhất khi áp dụng EDD.
**Kết quả này chỉ đúng cho mục tiêu $L_{\max}$.** Với một mục tiêu nghe rất giống — **số lượng công việc trễ** — EDD thuần không còn tối ưu; xem mục Bẫy thường gặp ngay sau đây. Đây chính là điểm học sinh hay nhầm nhất khi áp dụng EDD.
6
Sắp xếp bốn công việc theo thời hạn tăng dần: (4, 4), (2, 5), (3, 9), (5, 12) (ký hiệu (thời gian xử lý, thời hạn)). Tính thời điểm hoàn thành tích luỹ: $4, 6, 9, 14$ . Độ trễ tương ứng: $4-4=0$ , $6-5=1$ , $9-9=0$ , $14-12=2$ . Vậy $L_{\max}=2$ . Theo lập luận đổi chỗ đã chứng minh ở trên, không thứ tự nào cho $L_{\max}$ nhỏ hơn — kiểm chứng bằng duyệt toàn bộ cũng cho cùng giá trị 2. Vậy độ trễ lớn nhất nhỏ nhất có thể đạt được là $2$ .
Sắp xếp bốn công việc theo thời hạn tăng dần: (4, 4), (2, 5), (3, 9), (5, 12) (ký hiệu (thời gian xử lý, thời hạn)). Tính thời điểm hoàn thành tích luỹ: $4, 6, 9, 14$. Độ trễ tương ứng: $4-4=0$, $6-5=1$, $9-9=0$, $14-12=2$. Vậy $L_{\max}=2$. Theo lập luận đổi chỗ đã chứng minh ở trên, không thứ tự nào cho $L_{\max}$ nhỏ hơn — kiểm chứng bằng duyệt toàn bộ cũng cho cùng giá trị 2. Vậy độ trễ lớn nhất nhỏ nhất có thể đạt được là $2$.

Bẫy thường gặp — mục tiêu khác, tiêu chí có thể sai

EDD tối ưu cho $L_{\max}$ , nhưng KHÔNG tối ưu cho số công việc trễ. Xét ba công việc (thời gian xử lý, thời hạn): $A(1,1)$ , $B(1,3)$ , $C(2,2)$ . EDD sắp theo hạn tăng dần cho thứ tự $A, C, B$ : hoàn thành lúc $1, 3, 4$ — $C$ trễ ( $3>2$ ) và $B$ trễ ( $4>3$ ), tổng cộng 2 việc trễ. Nhưng thứ tự $A, B, C$ cho hoàn thành lúc $1, 2, 4$ — chỉ $C$ trễ ( $4>2$ ), tổng cộng 1 việc trễ, tốt hơn EDD. Ý tưởng: chấp nhận việc $C$ (xử lý lâu, $p=2$ ) trễ đổi lấy việc giữ đúng hạn cho hai việc ngắn $A, B$ . Bài toán 'tối thiểu số việc trễ' cần thuật toán Moore–Hodgson (EDD rồi loại bớt việc xử lý lâu nhất mỗi khi lịch trở nên bất khả thi), phức tạp hơn EDD thuần — không được dùng EDD cho mục tiêu này dù hai mục tiêu nghe rất giống nhau.

**EDD tối ưu cho $L_{\max}$, nhưng KHÔNG tối ưu cho số công việc trễ.** Xét ba công việc (thời gian xử lý, thời hạn): $A(1,1)$, $B(1,3)$, $C(2,2)$. EDD sắp theo hạn tăng dần cho thứ tự $A, C, B$: hoàn thành lúc $1, 3, 4$ — $C$ trễ ($3>2$) và $B$ trễ ($4>3$), tổng cộng **2 việc trễ**. Nhưng thứ tự $A, B, C$ cho hoàn thành lúc $1, 2, 4$ — chỉ $C$ trễ ($4>2$), tổng cộng **1 việc trễ**, tốt hơn EDD. Ý tưởng: chấp nhận việc $C$ (xử lý lâu, $p=2$) trễ đổi lấy việc giữ đúng hạn cho hai việc ngắn $A, B$. Bài toán 'tối thiểu số việc trễ' cần thuật toán Moore–Hodgson (EDD rồi loại bớt việc xử lý lâu nhất mỗi khi lịch trở nên bất khả thi), phức tạp hơn EDD thuần — **không được dùng EDD cho mục tiêu này** dù hai mục tiêu nghe rất giống nhau.

Mở rộng dành cho HSG — khi tham lam sai hoàn toàn

Kỹ thuật vượt chương trình

Mở rộng dành cho HSG: không phải cứ 'tham lam' là đúng. Bài đổi tiền kinh điển: có các loại tiền mệnh giá $\{1, 3, 4\}$ , cần đổi đúng $6$ đồng bằng ít tờ tiền nhất. Tham lam (luôn lấy tờ mệnh giá lớn nhất còn dùng được) cho: [4, 1, 1] — 3 tờ. Nhưng quy hoạch động (xét mọi cách) tìm được [3, 3] — chỉ 2 tờ, ít hơn. Tham lam sai vì mệnh giá $\{1,3,4\}$ không có tính chất 'mỗi mệnh giá chia hết cho mệnh giá nhỏ hơn liền kề' như hệ tiền Việt Nam — với hệ mệnh giá tuỳ ý, bài đổi tiền ít tờ nhất phải giải bằng quy hoạch động, không phải tham lam. Tiên quyết: khái niệm quy hoạch động sẽ học ở chuyên đề sau; ở đây chỉ cần nhận ra tham lam sai và vì sao.

**Mở rộng dành cho HSG:** không phải cứ 'tham lam' là đúng. Bài đổi tiền kinh điển: có các loại tiền mệnh giá $\{1, 3, 4\}$, cần đổi đúng $6$ đồng bằng ít tờ tiền nhất. Tham lam (luôn lấy tờ mệnh giá lớn nhất còn dùng được) cho: [4, 1, 1] — 3 tờ. Nhưng quy hoạch động (xét mọi cách) tìm được [3, 3] — chỉ 2 tờ, ít hơn. Tham lam sai vì mệnh giá $\{1,3,4\}$ không có tính chất 'mỗi mệnh giá chia hết cho mệnh giá nhỏ hơn liền kề' như hệ tiền Việt Nam — với hệ mệnh giá tuỳ ý, bài đổi tiền ít tờ nhất phải giải bằng quy hoạch động, không phải tham lam. Tiên quyết: khái niệm quy hoạch động sẽ học ở chuyên đề sau; ở đây chỉ cần nhận ra tham lam sai và vì sao.

Đổi 6 đồng với mệnh giá {1, 3, 4} — tham lam (4+1+1) thua quy hoạch động (3+3).

Luyện tập có hướng dẫn

Luyện tập độc lập

Thử thách

Tóm tắt

Lập luận đổi chỗ chứng minh một tiêu chí sắp xếp tham lam là tối ưu bằng cách chỉ xét đổi chỗ hai phần tử liền kề vi phạm tiêu chí, rồi chứng minh đổi chỗ không làm lời giải tệ hơn. Kỹ thuật này áp dụng được cho cả bài ghép chuỗi (Ví dụ 1) lẫn bài lập lịch (Ví dụ 2) — nhưng kết quả chỉ đúng cho đúng mục tiêu đã chứng minh: EDD tối ưu cho $L_{\max}$ , không tự động tối ưu cho một mục tiêu khác dù nghe tương tự. Và không phải bài nào tham lam cũng đúng — bài đổi tiền với mệnh giá tuỳ ý là phản ví dụ kinh điển.

**Lập luận đổi chỗ** chứng minh một tiêu chí sắp xếp tham lam là tối ưu bằng cách chỉ xét đổi chỗ hai phần tử liền kề vi phạm tiêu chí, rồi chứng minh đổi chỗ không làm lời giải tệ hơn. Kỹ thuật này áp dụng được cho cả bài ghép chuỗi (Ví dụ 1) lẫn bài lập lịch (Ví dụ 2) — nhưng **kết quả chỉ đúng cho đúng mục tiêu đã chứng minh**: EDD tối ưu cho $L_{\max}$, không tự động tối ưu cho một mục tiêu khác dù nghe tương tự. Và không phải bài nào tham lam cũng đúng — bài đổi tiền với mệnh giá tuỳ ý là phản ví dụ kinh điển.

Bài học sau áp dụng đúng khuôn lập luận đổi chỗ này cho một lớp bài toán kinh điển khác của HSG: chọn tối đa các khoảng thời gian không giao nhau, và một biến thể — phủ tất cả các khoảng bằng ít điểm nhất.