Greedy — Tham lam có chứng minh: Interval Scheduling và Huffman

TL;DR: Thuật toán greedy dựng nghiệm bằng cách chọn phương án tốt nhất tại chỗ (locally optimal) ở mỗi bước và không bao giờ quay lui. Greedy đúng khi bài toán có hai tính chất: greedy choice property (lựa chọn tham lam không chặn mất nghiệm tối ưu) và optimal substructure (nghiệm tối ưu của bài lớn chứa nghiệm tối ưu của bài con). Cách chứng minh là exchange argument: giả sử nghiệm tối ưu OPT khác greedy, hoán đổi một phần tử sang lựa chọn của greedy thì OPT không tệ đi, nên greedy cũng tối ưu. Greedy SAI khi thiếu một trong hai tính chất: 0/1 knapsack và coin change với mệnh giá lạ là hai counter-example (ví dụ làm greedy sai) kinh điển.

Cây Huffman cho sáu ký tự ở mục 5 chỉ tốn trung bình 2,24 bit mỗi ký tự, so với 3 bit của mã độ dài cố định. Nó đến từ một thuật toán greedy thuần túy: mỗi bước gộp hai node có tần suất nhỏ nhất, chỉ cần một min-heap. Niềm tin rằng chọn tham lam từng bước sẽ ra cây tối ưu phải được chứng minh.

1. Hình dung: người trả tiền thừa vs người đầu bếp tối ưu

Greedy là người trả tiền thừa dễ tính: khi trả 43.000đ, anh ta lấy tờ lớn nhất có thể (20k + 20k + 2k + 1k) và không bao giờ đổi ý. Với hệ mệnh giá Việt Nam (1k, 2k, 5k, 10k, 20k, 50k, 100k), cách này luôn cho số tờ ít nhất. Hệ mệnh giá như vậy gọi là canonical: lấy tờ lớn nhất luôn không làm hỏng kết quả cuối.

Khi greedy thất bại: đất nước khác có mệnh giá {1, 3, 4}, cần trả 6. Greedy: 4 + 1 + 1 = 3 đồng. Tối ưu: 3 + 3 = 2 đồng. Greedy chọn 4 (lớn nhất không vượt 6) nhưng chính đồng 4 làm mất tổ hợp tốt hơn. Muốn bắt được kiểu sai này, hãy làm tay vài ví dụ nhỏ trước khi tin một cách chọn, và chủ động đi tìm ví dụ làm nó sai.