Greedy vs Dynamic Programming: Perbedaan dan Kapan Menggunakannya

Pendahuluan

Ketika menghadapi masalah optimasi — seperti “apa rute tercepat?”, “berapa cara kembalian yang paling sedikit?”, atau “bagaimana memaksimalkan keuntungan?” — dua nama sering muncul: Greedy Algorithm dan Dynamic Programming (DP). Keduanya adalah paradigma pemecahan masalah yang kuat, tapi seringkali membuat bingung kapan harus memilih yang mana.

Kalau kamu sudah familiar dengan konsep dasar seperti yang dibahas di Pengenalan Struktur Data dan Algoritma untuk Pemula, artikel ini akan membawa pemahamanmu ke level berikutnya dengan membedah perbedaan fundamental keduanya secara praktis.

Singkatnya: Greedy selalu ambil pilihan terbaik saat ini, sementara DP mempertimbangkan semua kemungkinan secara menyeluruh. Tapi detail di balik perbedaan itu yang menentukan apakah kode kamu benar atau salah.

Membedah Konsep Greedy Algorithm

Greedy bekerja dengan prinsip sederhana: di setiap langkah, ambil pilihan yang terlihat paling optimal saat ini, tanpa melihat ke depan. Keputusan yang sudah dibuat tidak pernah di-backtrack.

Ciri khas Greedy:

• Keputusan lokal terbaik → diharapkan menghasilkan solusi global terbaik
• Tidak ada “penyesalan” — pilihan tidak bisa diubah
• Biasanya O(n log n) atau lebih cepat
• Tidak selalu menghasilkan solusi optimal, tapi sering cukup baik

Contoh klasik: Coin Change (versi Greedy)

Misalkan kamu punya koin Rp 500, Rp 200, Rp 100, Rp 50 dan perlu kembalian Rp 750. Greedy akan selalu ambil koin terbesar yang muat:

def greedy_coin_change(coins, amount):
    """
    Strategi greedy:
    selalu ambil koin terbesar yang masih bisa dipakai.

    Cocok untuk beberapa sistem koin tertentu (misalnya Rupiah),
    tetapi tidak selalu menghasilkan jumlah koin minimum
    pada semua sistem koin.
    """
    # Buat salinan dan urutkan dari terbesar ke terkecil
    sorted_coins = sorted(coins, reverse=True)

    result = []
    for coin in sorted_coins:
        while amount >= coin:
            result.append(coin)
            amount -= coin

    return result

# Contoh penggunaan
coins = [500, 200, 100, 50]
amount = 750
hasil = greedy_coin_change(coins, amount)
print(f"Koin yang digunakan: {hasil}")
print(f"Jumlah koin: {len(hasil)}")
# Output:
# Koin yang digunakan: [500, 200, 50]
# Jumlah koin: 3

Membedah Konsep Dynamic Programming (DP)

Dynamic Programming adalah pendekatan yang memecahkan masalah dengan membaginya menjadi submasalah yang lebih kecil dan menyimpan hasil dari submasalah tersebut untuk menghindari perhitungan ulang. Konsep ini sering dianalogikan seperti cara kerja tim navigasi di perusahaan logistik besar: alih-alih menghitung ulang rute dari nol setiap kali, mereka menyimpan hasil perhitungan rute sebelumnya dan menggunakannya kembali.

Ciri khas DP:

• Menyelesaikan submasalah terlebih dahulu dan menyimpan hasilnya (memoization atau tabulation)
• Submasalah yang sama tidak pernah dihitung dua kali
• Biasanya O(n²) atau lebih lambat daripada Greedy, tapi memberikan solusi yang dijamin optimal
• Cocok untuk masalah dengan overlapping subproblems dan optimal substructure

Dua pendekatan DP:

Contoh klasik: Coin Change (versi DP)

Kembali pada contoh Coin Change, kita gunakan DP untuk mencari jumlah koin minimum secara pasti — bahkan untuk sistem koin yang membuat Greedy gagal:

def dp_coin_change(coins, amount):
    """
    Strategi dynamic programming (bottom-up tabulation):
    hitung jumlah koin minimum untuk setiap nilai dari 0 hingga amount.

    Cocok untuk sistem koin apa pun, selalu menghasilkan solusi optimal.
    """
    # dp[i] = jumlah koin minimum untuk membuat nilai i
    # Inisialisasi dengan tak hingga (berarti "belum bisa dibuat")
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 koin dibutuhkan untuk membuat nilai 0

    for coin in coins:
        for x in range(coin, amount + 1):
            if dp[x - coin] != float('inf'):
                dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# Contoh penggunaan — sistem koin standar
coins = [500, 200, 100, 50]
amount = 750
print(f"Jumlah koin minimum: {dp_coin_change(coins, amount)}")
# Output: Jumlah koin minimum: 3

# Contoh penggunaan — kasus di mana Greedy gagal
# Sistem koin: [1, 3, 4], target: 6
# Greedy: 4+1+1 = 3 koin | DP: 3+3 = 2 koin
coins_tricky = [1, 3, 4]
amount_tricky = 6
print(f"Jumlah koin minimum (kasus sulit): {dp_coin_change(coins_tricky, amount_tricky)}")
# Output: Jumlah koin minimum (kasus sulit): 2

Visualisasi tabel DP untuk koin [1, 3, 4], target 6:

Nilai:  0   1   2   3   4   5   6
dp:     0   1   2   1   1   2   2

Penjelasan:
- dp[0] = 0  (tidak perlu koin)
- dp[1] = 1  (pakai koin 1)
- dp[2] = 2  (pakai koin 1+1)
- dp[3] = 1  (pakai koin 3)
- dp[4] = 1  (pakai koin 4)
- dp[5] = 2  (pakai koin 4+1)
- dp[6] = 2  (pakai koin 3+3) ← Greedy salah pilih 4+1+1=3 koin

Kapan Menggunakan Greedy vs DP

Pilihan antara Greedy dan DP bergantung pada karakteristik masalah:

Gunakan Greedy ketika:

• Masalah memiliki greedy choice property — keputusan lokal optimal selalu mengarah ke solusi global optimal
• Submasalah bersifat independen (pilihan satu tidak mempengaruhi yang lain)
• Kecepatan eksekusi adalah prioritas utama
• Contoh: Activity Selection, Huffman Coding, Prim’s MST

Gunakan DP ketika:

• Masalah memiliki overlapping subproblems — submasalah yang sama dihitung berkali-kali jika pakai rekursi biasa
• Masalah memiliki optimal substructure — solusi optimal terdiri dari solusi submasalah yang optimal
• Kamu membutuhkan solusi yang dijamin optimal
• Contoh: Knapsack, Longest Common Subsequence, Edit Distance

Tabel perbandingan cepat:

Kesimpulan

Kedua paradigma ini memiliki manfaat dan kekurangan masing-masing. Greedy adalah pilihan yang baik untuk masalah di mana keputusan lokal optimal selalu mengarah ke solusi global optimal — dan ketika kecepatan adalah prioritas. DP lebih cocok untuk masalah kompleks dengan overlapping subproblems di mana kamu tidak bisa “beruntung” dengan pilihan serakah.

Cara paling praktis untuk memilih: coba Greedy dulu, buktikan kebenarannya secara logis, dan beralih ke DP jika tidak bisa dibuktikan optimal.

Pertanyaan yang Sering Diajukan

Apakah Greedy selalu lebih cepat dari Dynamic Programming?

Secara umum ya, Greedy biasanya memiliki kompleksitas waktu yang lebih baik karena hanya membuat satu keputusan di setiap langkah tanpa menyimpan state. Namun kecepatan saja bukan alasan cukup untuk memilih Greedy — jika algoritma Greedy menghasilkan solusi yang salah untuk masalah tertentu, maka kecepatan tidak ada artinya. Selalu pertimbangkan kebenaran solusi terlebih dahulu, baru optimasi kecepatan.

Bagaimana cara membuktikan bahwa Greedy aman digunakan untuk suatu masalah?

Kamu perlu membuktikan dua properti: greedy choice property (pilihan lokal optimal tidak menutup jalan ke solusi global optimal) dan optimal substructure (solusi optimal masalah utama bisa dibangun dari solusi optimal submasalahnya). Jika salah satu tidak terpenuhi, Greedy bisa menghasilkan jawaban yang salah. Cara termudah adalah mencoba beberapa kasus tepi — jika menemukan satu kasus di mana Greedy gagal, langsung beralih ke DP.

Bisakah DP dan Greedy digunakan bersamaan dalam satu solusi?

Ya, ini bahkan cukup umum dalam algoritma lanjutan. Bayangkan seperti membangun sistem rekomendasi: kamu mungkin menggunakan DP untuk menghitung skor optimal tiap segmen, lalu Greedy untuk memilih rekomendasi final secara cepat dari kumpulan kandidat terbaik. Contoh nyata adalah algoritma Dijkstra yang menggunakan strategi Greedy (selalu proses node dengan jarak terpendek) namun membangun tabel jarak layaknya DP.

Mengapa Coin Change dengan koin [1, 3, 4] dan target 6 membuat Greedy gagal?

Greedy akan memilih koin 4 terlebih dahulu (terbesar yang muat), tersisa 2. Lalu memilih 1+1, total 3 koin. Padahal solusi optimal adalah 3+3 = 2 koin. Ini terjadi karena pilihan lokal terbaik (ambil 4 dulu) justru “mengunci” kita pada jalur yang tidak optimal. DP menghindari jebakan ini karena ia mengevaluasi semua kemungkinan untuk setiap nilai target secara sistematis sebelum memutuskan solusi terbaik.