Apakah algoritma tamak (greedy algorithms) dan bilakah ia berfungsi?

Question

Accepted Answer

**Algoritma tamak** membuat **pilihan optimal secara lokal** pada setiap langkah, berharap ia membawa ke optimum global. Ia sederhana dan cepat, tetapi hanya benar bila masalah memiliki **sifat greedy-choice** dan **struktur optimal**.

## Ideanya

Jangan pernah mempertimbangkan kembali pilihan masa lalu — berkomitmen pada opsi terbaik yang tersedia sekarang dan maju.

## Contoh: penukaran koin dengan koin kanonik

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

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

Ini optimal untuk koin AS, tetapi **gagal** untuk himpunan seperti {1, 3, 4} di mana tamak memberikan 4+1+1 untuk 6 daripada 3+3.

## Kapan tamak bekerja

- **Struktur optimal:** solusi optimal mengandung solusi-sub optimal.
- **Sifat greedy-choice:** optimum lokal adalah bagian dari optimum global.

Contoh yang berfungsi: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Kompleksitas

Biasanya cepat — sering O(n log n) setelah pengurutan.

## Jebakan

Tamak **tidak selalu benar**. Buktikan sifat greedy-choice atau uji terhadap baseline brute-force/DP sebelum mempercayainya.

## Mengapa penting

Ketika tamak berlaku, itu jauh lebih sederhana dan lebih cepat daripada DP atau brute force.

Mengetahui *kapan* itu valid — dan kapan itu diam-diam memberikan jawaban salah — adalah tanda kedewasaan algoritmik.

Banyak algoritma grafik fundamental adalah tamak di intinya.