Greedy algorithm là gì, và khi nào nó hoạt động?

Question

Accepted Answer

Một **greedy algorithm** (thuật toán tham lam) đưa ra **lựa chọn tối ưu cục bộ** tại mỗi bước, với hy vọng nó dẫn đến một tối ưu toàn cục. Nó đơn giản và nhanh, nhưng chỉ đúng khi bài toán có **tính chất greedy-choice** và **optimal substructure** (cấu trúc con tối ưu).

## Ý tưởng

Không bao giờ xem xét lại các lựa chọn trong quá khứ — cam kết với phương án tốt nhất ngay trước mắt và tiến lên.

## Ví dụ: đổi tiền với bộ tiền chuẩn

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # mệnh giá lớn nhất trước
        while amount >= coin:
            amount -= coin             # lấy nhiều nhất có thể
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

Điều này tối ưu với bộ tiền Mỹ, nhưng **thất bại** với các bộ như {1, 3, 4} khi greedy cho 4+1+1 với số tiền 6 thay vì 3+3.

## Khi nào greedy hoạt động

- **Optimal substructure:** một lời giải tối ưu chứa các lời giải con tối ưu.
- **Tính chất greedy-choice:** một tối ưu cục bộ là một phần của tối ưu toàn cục.

Các ví dụ hoạt động được: Dijkstra, Kruskal/Prim (MST), mã hóa Huffman, lập lịch khoảng (interval scheduling).

## Độ phức tạp

Thường nhanh — thường là O(n log n) sau khi sắp xếp.

## Những cạm bẫy

Greedy **không phải lúc nào cũng đúng**. Hãy chứng minh tính chất greedy-choice hoặc kiểm thử nó với một chuẩn cơ sở vét cạn/DP trước khi tin tưởng nó.

## Tại sao điều này quan trọng

Khi greedy áp dụng được, nó đơn giản và nhanh hơn nhiều so với DP hay vét cạn.

Biết *khi nào* nó hợp lệ — và khi nào nó âm thầm cho ra đáp án sai — là dấu hiệu của sự trưởng thành về thuật toán.

Nhiều thuật toán đồ thị nền tảng về bản chất là greedy.