Konsep Greedy

Beberapa masalah optimasi tampak rumit, tetapi bisa dipecahkan dengan strategi sederhana: ambil keputusan terbaik yang tersedia saat ini, tanpa menengok mundur. Inilah inti paradigma greedy (rakus). Algoritma greedy membangun solusi langkah demi langkah dengan memilih opsi yang tampak optimal secara lokal pada setiap titik keputusan. Pendekatan ini menarik karena cepat, ringkas, dan seringkali benar — tetapi tidak selalu. Pada Chapter ini kita akan memahami kapan greedy cocok dipakai, bagaimana membedakannya dari dynamic programming, dan mengapa sebagian besar sistem nyata (pembayaran uang, penjadwalan, kompresi data) bertumpu pada greedy.

Aturan: Pilih yang Optimal Lokal, Tanpa Mundur #

Algoritma greedy membangun solusi melalui serangkaian pilihan irreversible (tidak bisa dibatalkan). Pada setiap langkah, algoritma:

1. Mengidentifikasi himpunan kandidat pilihan yang valid pada saat itu.
2. Memilih satu kandidat berdasarkan kriteria tertentu (greedy choice).
3. Menambahkan kandidat tersebut ke solusi parsial.
4. Mengurangi masalah menjadi sub-masalah yang lebih kecil.
5. Mengulangi hingga tidak ada kandidat tersisa.

Karakteristik kunci adalah no backtracking — begitu pilihan dibuat, algoritma tidak pernah mempertimbangkannya ulang. Inilah yang membedakan greedy dari paradigma lain.

Mekanisme: Greedy vs Dynamic Programming #

Perbedaan paling sering membingungkan adalah greedy vs dynamic programming (DP). Keduanya memecah masalah menjadi sub-masalah, tetapi caranya berbeda secara fundamental.

Greedy tidak memeriksa ulang keputusan yang sudah diambil. DP menyimpan tabel dan dapat membandingkan beberapa pilihan secara bersamaan. Konsekuensinya, greedy lebih cepat tetapi rentan menghasilkan solusi suboptimal bila pilihan lokal tidak konsisten dengan pilihan global.

Contoh Klasik: Making Change dengan Canonical Denominations #

Misalkan kita ingin memberi kembalian sebesar amount menggunakan kombinasi koin dengan denominasi {1, 5, 10, 25} (sen). Tujuannya: minimalkan jumlah koin yang dipakai.

Strategi greedy: ambil koin denominasi terbesar yang tidak melebihi sisa kembalian. Strategi ini bekerja untuk canonical denominations seperti Euro atau Dolar Sen, tetapi gagal untuk denominasi sembarang.

#include <iostream>
#include <vector>
#include <algorithm>

// Greedy: minimalkan jumlah koin untuk kembalian `amount`
// denominations harus diurutkan descending
std::vector<int> greedyCoinChange(int amount,
                                  std::vector<int> denominations) {
    // Sort descending agar greedy pick denominasi terbesar dulu
    std::sort(denominations.begin(), denominations.end(),
              std::greater<int>());

    std::vector<int> result;
    for (int coin : denominations) {
        while (amount >= coin) {
            result.push_back(coin);
            amount -= coin;
        }
    }
    return result;
}

int main() {
    int amount = 63;
    std::vector<int> denoms = {1, 5, 10, 25};

    auto coins = greedyCoinChange(amount, denoms);
    std::cout << "Kembalian untuk " << amount << ":\n";
    std::cout << "  Koin dipakai: ";
    for (int c : coins) std::cout << c << ' ';
    std::cout << '\n';
    std::cout << "  Jumlah koin: " << coins.size() << '\n';

    return 0;
}

Output yang Dihasilkan:

Kembalian untuk 63:
  Koin dipakai: 25 25 10 1 1 1
  Jumlah koin: 6

Bedah Kode Baris-per-Baris #

1. std::sort(denominations.begin(), ..., std::greater<int>()): mengurutkan denominasi menurun agar greedy dapat mengambil koin terbesar yang masih muat dengan sisa kembalian.
2. for (int coin : denominations): iterasi denominasi dari terbesar ke terkecil. Untuk setiap koin, ambil sebanyak mungkin sebelum lanjut ke koin lebih kecil.
3. while (amount >= coin): selama sisa kembalian masih lebih besar atau sama dengan nilai koin, ambil koin ini. Inilah inti greedy choice.
4. result.push_back(coin); amount -= coin;: tambahkan koin ke solusi, lalu kurangi sisa kembalian. Pilihan ini tidak akan dibatalkan.
5. Output 25 25 10 1 1 1: greedy mengambil dua koin 25 (=50), satu koin 10 (=60), lalu tiga koin 1 (=63). Total 6 koin — yang memang optimal untuk denominasi standar ini.

Kapan Greedy Gagal #

Strategi greedy tidak selalu optimal. Contoh klasik adalah denominasi {1, 3, 4} dengan kembalian 6:

• Greedy: ambil 4, sisa 2 → ambil 1, ambil 1 → total 3 koin (4, 1, 1).
• Optimal: ambil 3, ambil 3 → total 2 koin (3, 3).

Greedy keliru karena memilih 4 (terbesar) tanpa menyadari dua koin 3 jauh lebih efisien. Untuk denominasi seperti ini, kita perlu dynamic programming.

#include <iostream>
#include <vector>
#include <algorithm>

// DP: minimalkan jumlah koin untuk kembalian amount
int dpCoinChange(int amount, const std::vector<int>& denoms) {
    const int INF = 1e9;
    std::vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        for (int c : denoms) {
            if (c <= i && dp[i - c] + 1 < dp[i]) {
                dp[i] = dp[i - c] + 1;
            }
        }
    }
    return dp[amount] >= INF ? -1 : dp[amount];
}

int main() {
    std::vector<int> denoms = {1, 3, 4};
    int amount = 6;
    std::cout << "Greedy pick 4 lalu 1+1 = 3 koin\n";
    std::cout << "DP optimal: " << dpCoinChange(amount, denoms) << " koin\n";
    return 0;
}

Output yang Dihasilkan:

Greedy pick 4 lalu 1+1 = 3 koin
DP optimal: 2 koin

Kode DP di atas membandingkan semua kombinasi koin dan menemukan solusi optimal 2 koin (3, 3), yang tidak ditemukan greedy.

Teori: Matroid dan Greedy Optimal #

Salah satu kerangka formal untuk greedy adalah matroid — struktur kombinatorial yang menjamin greedy selalu optimal. Matroid adalah pasangan (E, I) dengan E himpunan elemen dan I himpunan independent set, yang memenuhi tiga aksioma:

1. Himpunan kosong adalah independent.
2. Heredity: subset dari independent set juga independent.
3. Augmentation: bila |A| < |B| dengan A, B independent, maka ada elemen e ∈ B \ A sehingga A ∪ {e} independent.

Untuk masalah di atas matroid (misal MST dengan Kruskal), greedy selalu menghasilkan solusi optimal. Di luar matroid, greedy perlu dibuktikan secara terpisah — misalnya dengan exchange argument.

Karakteristik Masalah yang Cocok untuk Greedy #

Beberapa indikator bahwa greedy layak dicoba:

• Pilihan lokal yang jelas: ada kriteria natural seperti “terkecil”, “tercepat”, “termahal”.
• Solusi bertahap: solusi dibangun inkremental, tidak perlu membandingkan banyak kandidat sekaligus.
• Tidak ada dependensi maju: keputusan saat ini tidak dibatasi oleh keputusan yang akan datang.
• Optimal substructure terbukti: solusi optimal masalah dapat direduksi ke solusi optimal sub-masalah.

Aplikasi Nyata Greedy #

• Pembayaran uang: mesin ATM, kasir otomatis (dengan canonical denominations).
• Routing jaringan: Dijkstra, prim, kruskal — semua greedy.
• Kompresi data: Huffman coding memilih dua node frekuensi terendah.
• Penjadwalan CPU: shortest job first, earliest deadline first.
• Encoding: base64, base32 menggunakan strategi greedy encoding.
• Cache eviction: LRU merupakan strategi greedy berbasis recency.

Ringkasan #

• Greedy membangun solusi melalui pilihan lokal optimal yang tidak dapat dibatalkan.
• Perbedaan utama dengan DP: greedy tidak mengeksplorasi alternatif, DP ya.
• Greedy optimal bila memenuhi greedy-choice property dan optimal substructure.
• Making change dengan canonical denominations adalah contoh klasik greedy yang optimal.
• Denominasi sembarang (mis. {1, 3, 4}) menunjukkan greedy bisa gagal — di sinilah DP dibutuhkan.
• Matroid memberikan kerangka formal kapan greedy dijamin optimal.

Chapter berikutnya akan membahas Greedy Choice Property secara formal — sifat matematika yang menjadi syarat krusial kapan greedy dapat dipercaya menghasilkan solusi global optimal.