Backtracking menjelajah semua kemungkinan karena tidak berani memilih. Greedy berada di kutub yang sebaliknya: pada setiap langkah ia mengambil pilihan yang tampak paling menguntungkan saat itu — koin terbesar, kegiatan yang selesai paling awal — dan tidak pernah menoleh ke belakang. Hasilnya sangat cepat, biasanya satu kali sort plus satu lintasan, tetapi ada syarat yang tidak bisa ditawar: pilihan lokal terbaik harus terbukti menghasilkan solusi global terbaik, dan bukti itu tidak selalu ada. Chapter ini membangun dua greedy klasik — coin change dan interval scheduling — lalu sengaja membuat yang pertama gagal supaya pelajarannya menempel.

Greedy Coin Change: Koin Terbesar Dulu #

Untuk membentuk sejumlah uang dengan koin sesedikit mungkin, greedy memilih koin terbesar yang masih muat, berulang-ulang, sampai jumlahnya terbentuk. Program berikut menjalankan strategi itu pada koin rupiah, lalu pada sistem koin kecil yang akan memperlihatkan titik lemahnya. Sebagai pembanding, koinOptimal menghitung jawaban sejati dengan mencoba semua kombinasi secara rekursif — sah untuk kasus kecil seperti ini:

cpp 
// Dua algoritma greedy: coin change dan interval scheduling, plus batasnya.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

// Greedy coin change: selalu ambil koin terbesar yang masih muat.
// Mengembalikan jumlah koin terpakai, atau -1 bila jumlah tak terbentuk.
int koinGreedy(std::vector<int> koin, int jumlah, std::vector<int>& urutan) {
    std::sort(koin.begin(), koin.end(),
              [](int a, int b) { return a > b; });  // terbesar dulu
    urutan.clear();
    int sisa = jumlah;
    for (int k : koin) {
        while (sisa >= k) {
            sisa -= k;
            urutan.push_back(k);
        }
    }
    return (sisa == 0) ? static_cast<int>(urutan.size()) : -1;
}

// Solusi optimal untuk kasus kecil: coba semua pilihan secara rekursif.
int koinOptimal(const std::vector<int>& koin, int sisa) {
    if (sisa == 0) return 0;
    int terbaik = 1000000;
    for (int k : koin) {
        if (k <= sisa) {
            int coba = koinOptimal(koin, sisa - k);
            if (coba + 1 < terbaik) terbaik = coba + 1;
        }
    }
    return terbaik;
}

// Helper kecil: cetak vektor sebagai "4 1 1".
std::string rangkai(const std::vector<int>& data) {
    std::string hasil;
    for (std::size_t i = 0; i < data.size(); ++i) {
        if (i > 0) hasil += ' ';
        hasil += std::to_string(data[i]);
    }
    return hasil;
}

struct Kegiatan {
    std::string nama;
    int mulai;
    int selesai;
};

int main() {
    // Kasus 1: sistem koin rupiah (kanonik) — greedy memberi hasil optimal.
    std::vector<int> rupiah = {1000, 500, 200, 100, 50};
    std::vector<int> urutan;
    int total = koinGreedy(rupiah, 1750, urutan);
    std::cout << "Rupiah, jumlah 1750: greedy pakai " << total << " koin ("
              << rangkai(urutan) << ")\n";

    // Kasus 2: sistem koin non-kanonik — greedy gagal mencapai optimum.
    std::vector<int> nonKanonik = {4, 3, 1};
    int g = koinGreedy(nonKanonik, 6, urutan);
    int o = koinOptimal(nonKanonik, 6);
    std::cout << "Koin {4,3,1}, jumlah 6:\n";
    std::cout << "  greedy  : " << g << " koin (" << rangkai(urutan) << ")\n";
    std::cout << "  optimal : " << o << " koin (coba semua kombinasi)\n";

    // Interval scheduling: pilih kegiatan tanpa tumpang-tindih sebanyak mungkin.
    std::vector<Kegiatan> daftar = {
        {"Forum", 1, 3},       {"Lokakarya", 2, 5}, {"Demo", 4, 7},
        {"Kelas", 1, 8},       {"Webinar", 5, 9},   {"Sertifikasi", 8, 10},
    };
    std::sort(daftar.begin(), daftar.end(),
              [](const Kegiatan& a, const Kegiatan& b) {
                  return a.selesai < b.selesai;
              });
    std::vector<const Kegiatan*> pilih;
    int selesaiTerakhir = 0;
    for (const Kegiatan& k : daftar) {
        if (k.mulai >= selesaiTerakhir) {
            pilih.push_back(&k);
            selesaiTerakhir = k.selesai;
        }
    }
    std::cout << "Interval scheduling, dipilih " << pilih.size() << " dari "
              << daftar.size() << " kegiatan:\n";
    for (const Kegiatan* k : pilih) {
        std::cout << "  " << k->nama << " (" << k->mulai << "-"
                  << k->selesai << ")\n";
    }
    return 0;
}

Output yang Dihasilkan:

text 
Rupiah, jumlah 1750: greedy pakai 4 koin (1000 500 200 50)
Koin {4,3,1}, jumlah 6:
  greedy  : 3 koin (4 1 1)
  optimal : 2 koin (coba semua kombinasi)
Interval scheduling, dipilih 3 dari 6 kegiatan:
  Forum (1-3)
  Demo (4-7)
  Sertifikasi (8-10)

Bedah baris penting:

  1. Baris 10-11: koin diurutkan menurun dulu — greedy koin terbesar hanyalah sort plus pemindaian tunggal.
  2. Baris 13-18: while di dalam for menghabiskan koin terbesar selama masih muat; setiap pengambilan dicatat ke urutan untuk ditampilkan.
  3. Baris 20: sisa != 0 berarti jumlah tidak bisa dibentuk — greedy pun harus tahu kapan gagal total, bukan sekadar tidak optimal.
  4. Baris 24-35 (koinOptimal): rekursi mencoba setiap koin dari setiap sisa; ini brute force kecil yang menjadi hakim kebenaran.
  5. Baris 73-77: kegiatan diurutkan berdasarkan waktu selesai — inti dari interval scheduling.
  6. Baris 78-83: sebuah kegiatan dipilih bila mulai pada atau setelah kegiatan terakhir yang terpilih selesai.

Ketika Greedy Gagal: Sistem Koin Non-Kanonik #

Blok kedua output adalah pelajaran utama chapter ini. Untuk jumlah 6 dengan koin {4, 3, 1}, greedy mengambil 4, lalu terpaksa mengambil dua koin 1 — total tiga koin. Padahal solusi 3 + 3 hanya butuh dua. Greedy tidak salah menjalankan rencananya; rencananya sendiri tidak menjamin optimum.

Kenapa koin rupiah aman, sedangkan {4, 3, 1} tidak? Sistem seperti rupiah disebut kanonik: strukturnya (1, 50, 100, 200, 500, 1000) memastikan koin terbesar yang muat selalu aman diambil. Sifat ini harus dibuktikan per sistem koin — ia bukan sesuatu yang bisa diasumsikan. Ketika sistem tidak kanonik atau masalah sedikit berbeda, strategi umum yang selalu benar adalah menghitung semua subproblem secara sistematis; itu dynamic programming, dua chapter lagi. Untuk sekarang, cukup catat bahwa judul “greedy” tidak pernah menyertakan jaminan kebenaran.

Interval Scheduling: Greedy yang Terbukti Benar #

Kabar baiknya, ada masalah yang greedy-nya bisa dibuktikan. Interval scheduling: dari daftar kegiatan dengan jam mulai dan selesai, pilih sebanyak mungkin kegiatan yang tidak tumpang-tindih. Strateginya: urutkan berdasarkan waktu selesai, lalu ambil kegiatan yang selesai paling awal yang tidak bentrok dengan yang sudah dipilih. Intuisinya terasa adil — melepas kegiatan yang selesai lebih awal membebaskan waktu lebih banyak untuk sisanya.

Bukti lengkapnya memakai argumen penukaran (exchange argument): bandingkan solusi greedy dengan solusi optimal mana pun; kegiatan pertama greedy selesai paling awal, sehingga ia bisa menggantikan kegiatan pertama solusi optimal tanpa membuat satu pun kegiatan berikutnya bentrok. Ulangi pertukaran pada sisa kegiatan, dan solusi optimal berubah menjadi solusi greedy — berarti keduanya sama banyak. Hasil pada output memilih Forum, Demo, dan Sertifikasi: tiga kegiatan dari enam, dan tidak ada cara menempatkan empat.

Dua contoh hari ini menggarisbawahi pola yang sama: greedy itu murah (O(n log n) untuk sort, O(n) untuk lintasan) tetapi kontraknya ketat. Strategi ketiga menawarkan jalan tengah yang lebih tenang — pecah masalah menjadi versi kecil dari dirinya, selesaikan, lalu gabungkan. Itu divide and conquer, topik chapter berikutnya.

Rujukan resmi: std::sort dan std::to_string .