Greedy algorithm adalah strategi penyelesaian masalah optimasi yang membuat pilihan terbaik pada setiap langkah tanpa melihat ke depan secara menyeluruh. Harapannya, rangkaian local optimum akan menghasilkan global optimum. Pendekatan ini sederhana dan cepat, tetapi tidak selalu menghasilkan jawaban terbaik. Pada chapter ini kita akan mengimplementasikan tiga kasus klasik di Kotlin: coin change dengan pecahan Rupiah, activity selection untuk memilih maksimum aktivitas non-overlap, dan fractional knapsack. Pembaca juga akan melihat contoh konkret di mana greedy menghasilkan jawaban suboptimal sehingga membutuhkan dynamic programming.

Prinsip Greedy #

Greedy cocok untuk masalah yang memiliki dua sifat:

  1. Greedy choice property: pilihan lokal terbaik membentuk solusi global terbaik.
  2. Optimal substructure: solusi optimal untuk masalah mengandung solusi optimal untuk submasalahnya.
text 
Pola greedy:
1. Urutkan kandidat berdasarkan kriteria tertentu.
2. Ambil kandidat pertama yang valid.
3. Perbarui state.
4. Ulangi hingga tidak ada kandidat tersisa.

Kuncinya adalah memilih kriteria pengurutan yang tepat. Untuk coin change, urutkan pecahan dari besar ke kecil. Untuk activity selection, urutkan berdasarkan waktu selesai. Untuk fractional knapsack, urutkan berdasarkan rasio nilai per berat.

Kasus Sukses: Coin Change Rupiah dan Activity Selection #

Sistem pecahan Rupiah bersifat kanonik—setiap pecahan adalah kelipatan pecahan di bawahnya. Sifat ini membuat greedy selalu menghasilkan jumlah koin minimum. Activity selection mengoptimalkan jumlah aktivitas dengan menyortir berdasarkan waktu selesai sehingga setiap aktivitas yang diambil memberi ruang maksimal untuk aktivitas berikutnya.

Kasus Gagal: Pecahan Non-kanonik #

Untuk pecahan [1, 3, 4] dan target 6, greedy memilih 4 + 1 + 1 = 3 koin karena langsung mengambil pecahan terbesar yang tidak melebihi sisa. Padahal solusi optimal adalah 3 + 3 = 2 koin. Inilah kapan greedy gagal dan harus diganti dengan dynamic programming yang mengeksplorasi semua kemungkinan.

Implementasi Greedy Algorithms #

kotlin 
// Demo Greedy Algorithms: coin change, activity selection, Huffman-like.

// === Coin change greedy ===
// Pecahan: [100000, 50000, 20000, 10000, 5000, 2000, 1000, 500, 100]
fun coinChangeGreedy(amount: Int, pecahan: IntArray): Map<Int, Int> {
    val sortedPecahan = pecahan.sortedArrayDescending()
    val result = mutableMapOf<Int, Int>()
    var sisa = amount
    for (p in sortedPecahan) {
        if (sisa <= 0) break
        val count = sisa / p
        if (count > 0) {
            result[p] = count
            sisa -= count * p
        }
    }
    if (sisa != 0) {
        result[-1] = sisa  // sisa yang tidak bisa dipecah
    }
    return result
}

// === Activity selection: pilih maksimum aktivitas non-overlap ===
data class Activity(val nama: String, val start: Int, val finish: Int)

fun activitySelection(activities: List<Activity>): List<Activity> {
    // Sort by finish time
    val sorted = activities.sortedBy { it.finish }
    val result = mutableListOf<Activity>()
    var lastFinish = 0
    for (a in sorted) {
        if (a.start >= lastFinish) {
            result.add(a)
            lastFinish = a.finish
        }
    }
    return result
}

// === Greedy tidak selalu optimal: coin change dengan pecahan aneh ===
// Pecahan [1, 3, 4], target 6
// Greedy: 4 + 1 + 1 = 3 koin
// Optimal: 3 + 3 = 2 koin
fun coinChangeGreedyCount(amount: Int, pecahan: IntArray): Int {
    val sorted = pecahan.sortedArrayDescending()
    var sisa = amount
    var count = 0
    for (p in sorted) {
        while (sisa >= p) {
            sisa -= p
            count++
        }
    }
    return if (sisa == 0) count else -1
}

// === Fractional knapsack (greedy optimal) ===
data class Item(val nama: String, val berat: Int, val nilai: Int) {
    val rasio: Double get() = nilai.toDouble() / berat
}

fun fractionalKnapsack(kapasitas: Int, items: List<Item>): Pair<Double, List<String>> {
    val sorted = items.sortedByDescending { it.rasio }
    val ambil = mutableListOf<String>()
    var sisa = kapasitas
    var totalNilai = 0.0
    for (item in sorted) {
        if (sisa <= 0) break
        if (item.berat <= sisa) {
            ambil.add("${item.nama} (penuh, berat=${item.berat}, nilai=${item.nilai})")
            totalNilai += item.nilai
            sisa -= item.berat
        } else {
            val fraksi = sisa.toDouble() / item.berat
            ambil.add("${item.nama} (${"%.2f".format(fraksi * 100)}%, berat=$sisa, nilai=${item.nilai * fraksi})")
            totalNilai += item.nilai * fraksi
            sisa = 0
        }
    }
    return totalNilai to ambil
}

fun main() {
    println("=== Demo Greedy Algorithms ===")

    println("--- Coin change greedy (Rupiah) ---")
    val pecahan = intArrayOf(100000, 50000, 20000, 10000, 5000, 2000, 1000, 500, 100)
    val amounts = listOf(135700, 50000, 178900, 99900)
    amounts.forEach { amt ->
        val result = coinChangeGreedy(amt, pecahan)
        println("Rp$amt -> $result")
    }

    println()
    println("--- Activity selection ---")
    val activities = listOf(
        Activity("A", 1, 4),
        Activity("B", 3, 5),
        Activity("C", 0, 6),
        Activity("D", 5, 7),
        Activity("E", 3, 9),
        Activity("F", 5, 9),
        Activity("G", 6, 10),
        Activity("H", 8, 11),
        Activity("I", 8, 12),
        Activity("J", 2, 14),
        Activity("K", 12, 16)
    )
    val selected = activitySelection(activities)
    println("Total aktivitas: ${activities.size}")
    println("Aktivitas terpilih: ${selected.size}")
    selected.forEach { println("  ${it.nama}: start=${it.start}, finish=${it.finish}") }

    println()
    println("--- Greedy tidak optimal: pecahan [1,3,4], target 6 ---")
    val weirdPecahan = intArrayOf(1, 3, 4)
    println("Greedy: ${coinChangeGreedyCount(6, weirdPecahan)} koin (4 + 1 + 1)")
    println("Optimal: 2 koin (3 + 3)")

    println()
    println("--- Fractional knapsack ---")
    val items = listOf(
        Item("Emas", 10, 60),
        Item("Perak", 20, 100),
        Item("Perunggu", 30, 120)
    )
    val (nilai, ambil) = fractionalKnapsack(50, items)
    println("Kapasitas: 50, items: ${items.map { "${it.nama}(b=${it.berat},n=${it.nilai})" }}")
    println("Ambil:")
    ambil.forEach { println("  $it") }
    println("Total nilai: ${"%.2f".format(nilai)}")
}

Output yang Dihasilkan:

text 
=== Demo Greedy Algorithms ===
--- Coin change greedy (Rupiah) ---
Rp135700 -> {100000=1, 20000=1, 10000=1, 5000=1, 500=1, 100=2}
Rp50000 -> {50000=1}
Rp178900 -> {100000=1, 50000=1, 20000=1, 5000=1, 2000=1, 1000=1, 500=1, 100=4}
Rp99900 -> {50000=1, 20000=2, 5000=1, 2000=2, 500=1, 100=4}

--- Activity selection ---
Total aktivitas: 11
Aktivitas terpilih: 4
  A: start=1, finish=4
  D: start=5, finish=7
  H: start=8, finish=11
  K: start=12, finish=16

--- Greedy tidak optimal: pecahan [1,3,4], target 6 ---
Greedy: 3 koin (4 + 1 + 1)
Optimal: 2 koin (3 + 3)

--- Fractional knapsack ---
Kapasitas: 50, items: [Emas(b=10,n=60), Perak(b=20,n=100), Perunggu(b=30,n=120)]
Ambil:
  Emas (penuh, berat=10, nilai=60)
  Perak (penuh, berat=20, nilai=100)
  Perunggu (66.67%, berat=20, nilai=80.0)
Total nilai: 240.00

Bedah Kode Baris-per-Baris #

Mari kita amati bagian kunci:

  1. coinChangeGreedy (baris 5-21): Mengurutkan pecahan dari besar ke kecil dengan sortedArrayDescending(). Untuk setiap pecahan, hitung berapa banyak yang bisa diambil dengan pembagian bulat sisa / p. Simpan ke map dan kurangi sisa. Bila ada sisa yang tidak bisa dipecah (misalnya pecahan terkecil 100 dan sisa = 50), hasil ditandai dengan key -1.
  2. activitySelection (baris 26-38): Mengurutkan aktivitas berdasarkan finish menggunakan sortedBy { it.finish }. Loop mengambil aktivitas yang start >= lastFinish, lalu memperbarui lastFinish ke waktu selesai aktivitas tersebut. Strategi ini optimal karena aktivitas yang selesai lebih awal memberi ruang terbanyak untuk aktivitas berikutnya.
  3. coinChangeGreedyCount (baris 44-55): Versi greedy untuk pecahan non-kanonik. Loop while (sisa >= p) mengambil pecahan berulang hingga tidak cukup. Hasil 3 koin untuk target 6 dengan pecahan [1,3,4] membuktikan greedy gagal memberi solusi optimal (yang sebenarnya 2 koin).
  4. fractionalKnapsack (baris 62-81): Mengurutkan item berdasarkan rasio nilai per berat (sortedByDescending { it.rasio }). Bila item muat sepenuhnya (item.berat <= sisa), ambil seluruhnya. Bila tidak, ambil fraksi sesuai kapasitas tersisa (sisa.toDouble() / item.berat). Greedy optimal di sini karena masalah fractional knapsack memenuhi greedy choice property—setiap unit berat yang tersisa selalu diisi oleh item dengan rasio tertinggi yang tersedia.

Kapan Greedy Cocok #

Greedy unggul ketika masalah memiliki greedy choice property yang jelas: coin change kanonik, activity selection, fractional knapsack, Huffman coding, algoritma Kruskal/Prim untuk MST, dan algoritma Dijkstra untuk shortest path. Kompleksitas greedy biasanya O(n log n) karena langkah pengurutan, jauh lebih cepat dari DP yang sering O(n²) atau O(n * W).

Penutup #

Greedy adalah pendekatan sederhana dan cepat untuk masalah optimasi dengan sifat greedy choice property. Ketika sifat tersebut tidak terpenuhi, jawaban greedy bisa suboptimal dan dynamic programming menjadi pilihan yang lebih aman. Pada chapter berikutnya kita akan mempelajari dynamic programming secara mendalam.

Referensi #

Referensi Lanjutan #