Backtracking pada Bab sebelumnya menjelajahi cabang demi cabang sampai seluruh ruang solusi tersapu. Kadang kita tidak sanggup menunggu seteliti itu — data terlalu besar, batas waktu terlalu ketat — dan muncul godaan besar: ambil saja pilihan yang paling menguntungkan saat ini, lalu bergerak maju tanpa pernah menoleh. Strategi itu bernama greedy algorithm. Greedy menakjubkan ketika berhasil: kode pendek, eksekusi kilat, dan hasilnya terbukti optimal. Greedy juga berbahaya ketika salah pilih: kode yang sama menghasilkan jawaban yang jauh dari optimal tanpa memberi peringatan apa pun. Bab ini menguji greedy pada tiga persoalan klasik — kembalian koin, fractional knapsack, dan penjadwalan interval — sambil membedah kapan keputusan lokal menghasilkan hasil global.

Kembalian Koin dan Jebakan Denominasi #

Pertanyaan pertama greedy yang wajar: berapa keping koin untuk kembalian? Strateginya intuitif — ambil koin bernilai terbesar yang masih muat, ulangi pada sisanya. Pada sistem koin rupiah strategi ini benar:

java GreedyKoin.java 
import java.util.Arrays;

public class GreedyKoin {

    public static void main(String[] args) {
        // Denominasi koin rupiah, urut menurun untuk strategi greedy.
        int[] denominasi = {10000, 5000, 2000, 1000, 500, 200, 100};
        int jumlah = 73500;

        System.out.println("=== Kembalian Rp" + jumlah + " dengan greedy ===");
        int[] hasil = kembalianGreedy(denominasi, jumlah);
        for (int i = 0; i < denominasi.length; i++) {
            if (hasil[i] > 0) {
                System.out.printf("  Rp%-6d x %d%n", denominasi[i], hasil[i]);
            }
        }
        System.out.println("Total keping koin: " + totalKeping(hasil));

        System.out.println();
        System.out.println("=== Kontra-contoh: denominasi {25, 10, 1}, jumlah 30 ===");
        int[] khayalan = {25, 10, 1};
        int[] hasilGreedy = kembalianGreedy(khayalan, 30);
        System.out.println("Greedy  : " + deskripsi(khayalan, hasilGreedy)
                + " -> " + totalKeping(hasilGreedy) + " keping");
        System.out.println("Optimal : " + koinMinDP(khayalan, 30)
                + " keping (dihitung dengan dynamic programming)");
    }

    // Greedy: ambil koin terbesar yang masih muat, ulangi pada sisanya.
    static int[] kembalianGreedy(int[] denominasi, int jumlah) {
        int[] hasil = new int[denominasi.length];
        int sisa = jumlah;
        for (int i = 0; i < denominasi.length && sisa > 0; i++) {
            hasil[i] = sisa / denominasi[i];
            sisa %= denominasi[i];
        }
        return hasil;
    }

    // Pembanding optimal: coin change via tabel DP sederhana.
    static int koinMinDP(int[] koin, int jumlah) {
        int[] terbaik = new int[jumlah + 1];
        Arrays.fill(terbaik, Integer.MAX_VALUE);
        terbaik[0] = 0;
        for (int n = 1; n <= jumlah; n++) {
            for (int k : koin) {
                if (k <= n && terbaik[n - k] != Integer.MAX_VALUE) {
                    terbaik[n] = Math.min(terbaik[n], terbaik[n - k] + 1);
                }
            }
        }
        return terbaik[jumlah];
    }

    static int totalKeping(int[] hasil) {
        int total = 0;
        for (int h : hasil) {
            total += h;
        }
        return total;
    }

    static String deskripsi(int[] denominasi, int[] hasil) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < denominasi.length; i++) {
            if (hasil[i] > 0) {
                if (!sb.isEmpty()) {
                    sb.append(" + ");
                }
                sb.append(denominasi[i]).append("x").append(hasil[i]);
            }
        }
        return sb.toString();
    }
}

Output yang Dihasilkan:

text 
=== Kembalian Rp73500 dengan greedy ===
  Rp10000  x 7
  Rp2000   x 1
  Rp1000   x 1
  Rp500    x 1
Total keping koin: 10

=== Kontra-contoh: denominasi {25, 10, 1}, jumlah 30 ===
Greedy  : 25x1 + 1x5 -> 6 keping
Optimal : 3 keping (dihitung dengan dynamic programming)

Pada Rp73500 greedy menghasilkan 10 keping (tujuh Rp10000, satu Rp2000, satu Rp1000, satu Rp500) — dan itu memang optimal. Namun bagian kedua output memperlihatkan runtuhnya jaminan: pada sistem koin {25, 10, 1} untuk jumlah 30, greedy mengambil 25 lalu lima keping 1 (total 6 keping), padahal solusi optimal cukup tiga keping 10. Kesimpulannya tegas: greedy coin change benar hanya untuk sistem denominasi canonical seperti rupiah yang setiap koinnya paling tidak 2× koin di bawahnya; untuk sistem umum, jawaban optimal harus dihitung dynamic programming. Method koinMinDP adalah pembandingnya — tabel kecil yang mencoba semua kombinasi secara sistematis.

Fractional Knapsack Menerima Potongan #

Persoalan knapsack klasik: tas berkapasitas terbatas, barang bernilai dengan berat berbeda, pilih muatan bernilai maksimum. Varian fractional membolehkan barang dipotong — kopi boleh dibawa 20 dari 30 kg. Kebebasan memotong inilah yang membuat greedy terbukti optimal: urutkan barang berdasarkan rasio nilai per berat, lalu isi tas dari rasio tertinggi:

java KnapsackFraksional.java 
import java.util.Arrays;
import java.util.Comparator;

public class KnapsackFraksional {

    record Barang(String nama, int nilai, int berat) { }

    public static void main(String[] args) {
        Barang[] barang = {
            new Barang("Beras premium", 60, 10),
            new Barang("Gula pasir", 100, 20),
            new Barang("Kopi instan", 120, 30),
        };
        int kapasitas = 50;

        // Greedy: urutkan berdasarkan rasio nilai/berat menurun.
        Barang[] urut = barang.clone();
        Arrays.sort(urut, Comparator
                .comparingDouble((Barang b) -> (double) b.nilai() / b.berat())
                .reversed());

        System.out.println("Kapasitas tas: " + kapasitas + " kg");
        System.out.println();
        double totalNilai = 0;
        int sisa = kapasitas;
        for (Barang b : urut) {
            if (sisa <= 0) {
                break;
            }
            int ambil = Math.min(b.berat(), sisa);
            double fraksi = (double) ambil / b.berat();
            totalNilai += b.nilai() * fraksi;
            System.out.printf("Ambil %-14s: %2d/%2d kg (rasio nilai/berat %.1f)%n",
                    b.nama(), ambil, b.berat(), (double) b.nilai() / b.berat());
            sisa -= ambil;
        }
        System.out.println();
        System.out.printf("Total nilai maksimum: %.0f%n", totalNilai);
    }
}

Output yang Dihasilkan:

text 
Kapasitas tas: 50 kg

Ambil Beras premium : 10/10 kg (rasio nilai/berat 6.0)
Ambil Gula pasir    : 20/20 kg (rasio nilai/berat 5.0)
Ambil Kopi instan   : 20/30 kg (rasio nilai/berat 4.0)

Total nilai maksimum: 240

Tas 50 kg diisi penuh: seluruh beras (rasio 6,0), seluruh gula (rasio 5,0), lalu 20 dari 30 kg kopi (rasio 4,0) — total nilai 240, dan angka itu bisa dibuktikan optimal lewat argumen tukar: setiap kilogram yang dipindahkan dari rasio rendah ke rasio tinggi pasti menurunkan nilai. Perhatikan bedanya dengan varian 0/1 knapsack yang melarang pemotongan: di sana greedy rasio bisa salah besar (barang rasio tertinggi bisa mengunci kapasitas), dan solusi optimal menuntut dynamic programming — materi Bab berikutnya.

Interval Scheduling Memilih Selesai Terawal #

Persoalan ketiga: pilih sebanyak mungkin rapat yang tidak bertumpang tindih dari satu daftar jadwal. Greedy yang terbukti optimal adalah “rapat yang selesai paling awal lebih dulu” — rapat yang cepat selesai membebaskan ruangan secepat mungkin bagi rapat berikutnya:

java PenjadwalanRapat.java 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class PenjadwalanRapat {

    record Rapat(String nama, int mulai, int selesai) { }

    public static void main(String[] args) {
        Rapat[] jadwal = {
            new Rapat("Rapat A", 8, 10),
            new Rapat("Rapat B", 9, 11),
            new Rapat("Rapat C", 10, 12),
            new Rapat("Rapat D", 11, 13),
            new Rapat("Rapat E", 12, 15),
            new Rapat("Rapat F", 14, 16),
        };

        System.out.println("=== Strategi tepat: rapat selesai paling awal ===");
        pilih(jadwal, Comparator.comparingInt(Rapat::selesai));

        System.out.println();
        System.out.println("=== Kontra-contoh strategi greedy lain ===");

        // Greedy "mulai paling awal" kalah: rapat panjang memblok empat rapat pendek.
        Rapat[] ujiMulai = {
            new Rapat("Rapat Panjang", 8, 12),
            new Rapat("Rapat 1", 8, 9),
            new Rapat("Rapat 2", 9, 10),
            new Rapat("Rapat 3", 10, 11),
            new Rapat("Rapat 4", 11, 12),
        };
        System.out.println("Data 1 (greedy mulai terawal):");
        pilih(ujiMulai, Comparator.comparingInt(Rapat::mulai));
        System.out.println("Data 1 (greedy selesai terawal):");
        pilih(ujiMulai, Comparator.comparingInt(Rapat::selesai));

        // Greedy "durasi tersingkat" kalah: rapat pendek menutup dua rapat panjang.
        Rapat[] ujiDurasi = {
            new Rapat("Rapat Satu", 8, 12),
            new Rapat("Rapat Singkat", 10, 13),
            new Rapat("Rapat Dua", 12, 16),
        };
        System.out.println("Data 2 (greedy durasi tersingkat):");
        pilih(ujiDurasi, Comparator.comparingInt(r -> r.selesai() - r.mulai()));
        System.out.println("Data 2 (greedy selesai terawal):");
        pilih(ujiDurasi, Comparator.comparingInt(Rapat::selesai));
    }

    // Greedy generik: urutkan sesuai strategi, ambil rapat yang tidak bertumpang tindih.
    static void pilih(Rapat[] jadwal, Comparator<Rapat> strategi) {
        Rapat[] urut = jadwal.clone();
        Arrays.sort(urut, strategi);

        List<Rapat> terpilih = new ArrayList<>();
        int selesaiTerakhir = Integer.MIN_VALUE;
        for (Rapat r : urut) {
            if (r.mulai() >= selesaiTerakhir) {
                terpilih.add(r);
                selesaiTerakhir = r.selesai();
            }
        }

        StringBuilder sb = new StringBuilder("  Terpilih: ");
        for (int i = 0; i < terpilih.size(); i++) {
            if (i > 0) {
                sb.append(", ");
            }
            Rapat r = terpilih.get(i);
            sb.append(r.nama()).append(" (").append(r.mulai()).append("-")
                    .append(r.selesai()).append(")");
        }
        System.out.println(sb);
        System.out.println("  Jumlah rapat: " + terpilih.size());
    }
}

Output yang Dihasilkan:

text 
=== Strategi tepat: rapat selesai paling awal ===
  Terpilih: Rapat A (8-10), Rapat C (10-12), Rapat E (12-15)
  Jumlah rapat: 3

=== Kontra-contoh strategi greedy lain ===
Data 1 (greedy mulai terawal):
  Terpilih: Rapat Panjang (8-12)
  Jumlah rapat: 1
Data 1 (greedy selesai terawal):
  Terpilih: Rapat 1 (8-9), Rapat 2 (9-10), Rapat 3 (10-11), Rapat 4 (11-12)
  Jumlah rapat: 4
Data 2 (greedy durasi tersingkat):
  Terpilih: Rapat Singkat (10-13)
  Jumlah rapat: 1
Data 2 (greedy selesai terawal):
  Terpilih: Rapat Satu (8-12), Rapat Dua (12-16)
  Jumlah rapat: 2

Pada jadwal utama, greedy selesai-terawal memilih tiga rapat: A (8-10), C (10-12), E (12-15). Bagian kontra-contoh memperlihatkan mengapa kriteria pengurutan menentukan segalanya. Mari kita bedah:

  1. Baris 73-79 (loop pemilihan): setelah terurut, pemilihan hanya satu sapuan — rapat diambil bila mulai >= selesaiTerakhir, lalu penanda bergeser. Total O(n log n) untuk sorting, O(n) untuk pemilihan.
  2. Data 1: greedy “mulai terawal” terjebak mengambil Rapat Panjang (8-12) yang memblok empat rapat pendek berurutan — hasil 1 lawan 4. Rapat yang dimulai pagi belum tentu pilihan baik; yang menentukan adalah seberapa cepat ruangan kembali bebas.
  3. Data 2: greedy “durasi tersingkat” mengambil Rapat Singkat (10-13) yang menutup jalur dua rapat panjang 8-12 dan 12-16 — hasil 1 lawan 2. Durasi pendek tidak menolong bila posisinya melintasi dua rapat lain.
  4. Mengapa selesai-terawal menang: argumen tukar (exchange argument) — solusi optimal mana pun yang rapat pertamanya bukan yang selesai paling awal bisa ditukar rapatnya dengan yang selesai lebih awal tanpa mengurangi jumlah, karena semua rapat setelahnya punya ruang gerak yang makin longgar.

Kapan Greedy Bisa Dipercaya #

Pola pada ketiga contoh menghasilkan daftar periksa yang sama. Greedy layak dipakai bila persoalan punya dua sifat: substructure — solusi optimal tersusun dari solusi optimal subpersoalan yang lebih kecil; dan greedy choice property — pilihan lokal terbaik tidak pernah menutup jalan menuju solusi global terbaik. Kedua sifat tersebut harus dibuktikan (biasanya lewat exchange argument), bukan ditebak. Tanpa bukti, greedy hanyalah heuristik: berguna untuk perkiraan cepat, berbahaya untuk jawaban yang harus tepat.

Greedy menyelesaikan persoalan yang strukturnya ramah terhadap pilihan lokal. Namun keluarga persoalan lain — fibonacci rekursif, 0/1 knapsack, rod cutting — menyembunyikan jebakan berbeda: subpersoalan yang sama dihitung berulang kali. Bab berikutnya, dynamic programming, menyelesaikannya dengan satu ide sederhana: ingat hasil yang sudah dihitung.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

GreedyKoin.java

Unduh berkas
java 
import java.util.Arrays;

public class GreedyKoin {

    public static void main(String[] args) {
        // Denominasi koin rupiah, urut menurun untuk strategi greedy.
        int[] denominasi = {10000, 5000, 2000, 1000, 500, 200, 100};
        int jumlah = 73500;

        System.out.println("=== Kembalian Rp" + jumlah + " dengan greedy ===");
        int[] hasil = kembalianGreedy(denominasi, jumlah);
        for (int i = 0; i < denominasi.length; i++) {
            if (hasil[i] > 0) {
                System.out.printf("  Rp%-6d x %d%n", denominasi[i], hasil[i]);
            }
        }
        System.out.println("Total keping koin: " + totalKeping(hasil));

        System.out.println();
        System.out.println("=== Kontra-contoh: denominasi {25, 10, 1}, jumlah 30 ===");
        int[] khayalan = {25, 10, 1};
        int[] hasilGreedy = kembalianGreedy(khayalan, 30);
        System.out.println("Greedy  : " + deskripsi(khayalan, hasilGreedy)
                + " -> " + totalKeping(hasilGreedy) + " keping");
        System.out.println("Optimal : " + koinMinDP(khayalan, 30)
                + " keping (dihitung dengan dynamic programming)");
    }

    // Greedy: ambil koin terbesar yang masih muat, ulangi pada sisanya.
    static int[] kembalianGreedy(int[] denominasi, int jumlah) {
        int[] hasil = new int[denominasi.length];
        int sisa = jumlah;
        for (int i = 0; i < denominasi.length && sisa > 0; i++) {
            hasil[i] = sisa / denominasi[i];
            sisa %= denominasi[i];
        }
        return hasil;
    }

    // Pembanding optimal: coin change via tabel DP sederhana.
    static int koinMinDP(int[] koin, int jumlah) {
        int[] terbaik = new int[jumlah + 1];
        Arrays.fill(terbaik, Integer.MAX_VALUE);
        terbaik[0] = 0;
        for (int n = 1; n <= jumlah; n++) {
            for (int k : koin) {
                if (k <= n && terbaik[n - k] != Integer.MAX_VALUE) {
                    terbaik[n] = Math.min(terbaik[n], terbaik[n - k] + 1);
                }
            }
        }
        return terbaik[jumlah];
    }

    static int totalKeping(int[] hasil) {
        int total = 0;
        for (int h : hasil) {
            total += h;
        }
        return total;
    }

    static String deskripsi(int[] denominasi, int[] hasil) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < denominasi.length; i++) {
            if (hasil[i] > 0) {
                if (!sb.isEmpty()) {
                    sb.append(" + ");
                }
                sb.append(denominasi[i]).append("x").append(hasil[i]);
            }
        }
        return sb.toString();
    }
}

KnapsackFraksional.java

Unduh berkas
java 
import java.util.Arrays;
import java.util.Comparator;

public class KnapsackFraksional {

    record Barang(String nama, int nilai, int berat) { }

    public static void main(String[] args) {
        Barang[] barang = {
            new Barang("Beras premium", 60, 10),
            new Barang("Gula pasir", 100, 20),
            new Barang("Kopi instan", 120, 30),
        };
        int kapasitas = 50;

        // Greedy: urutkan berdasarkan rasio nilai/berat menurun.
        Barang[] urut = barang.clone();
        Arrays.sort(urut, Comparator
                .comparingDouble((Barang b) -> (double) b.nilai() / b.berat())
                .reversed());

        System.out.println("Kapasitas tas: " + kapasitas + " kg");
        System.out.println();
        double totalNilai = 0;
        int sisa = kapasitas;
        for (Barang b : urut) {
            if (sisa <= 0) {
                break;
            }
            int ambil = Math.min(b.berat(), sisa);
            double fraksi = (double) ambil / b.berat();
            totalNilai += b.nilai() * fraksi;
            System.out.printf("Ambil %-14s: %2d/%2d kg (rasio nilai/berat %.1f)%n",
                    b.nama(), ambil, b.berat(), (double) b.nilai() / b.berat());
            sisa -= ambil;
        }
        System.out.println();
        System.out.printf("Total nilai maksimum: %.0f%n", totalNilai);
    }
}

PenjadwalanRapat.java

Unduh berkas
java 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class PenjadwalanRapat {

    record Rapat(String nama, int mulai, int selesai) { }

    public static void main(String[] args) {
        Rapat[] jadwal = {
            new Rapat("Rapat A", 8, 10),
            new Rapat("Rapat B", 9, 11),
            new Rapat("Rapat C", 10, 12),
            new Rapat("Rapat D", 11, 13),
            new Rapat("Rapat E", 12, 15),
            new Rapat("Rapat F", 14, 16),
        };

        System.out.println("=== Strategi tepat: rapat selesai paling awal ===");
        pilih(jadwal, Comparator.comparingInt(Rapat::selesai));

        System.out.println();
        System.out.println("=== Kontra-contoh strategi greedy lain ===");

        // Greedy "mulai paling awal" kalah: rapat panjang memblok empat rapat pendek.
        Rapat[] ujiMulai = {
            new Rapat("Rapat Panjang", 8, 12),
            new Rapat("Rapat 1", 8, 9),
            new Rapat("Rapat 2", 9, 10),
            new Rapat("Rapat 3", 10, 11),
            new Rapat("Rapat 4", 11, 12),
        };
        System.out.println("Data 1 (greedy mulai terawal):");
        pilih(ujiMulai, Comparator.comparingInt(Rapat::mulai));
        System.out.println("Data 1 (greedy selesai terawal):");
        pilih(ujiMulai, Comparator.comparingInt(Rapat::selesai));

        // Greedy "durasi tersingkat" kalah: rapat pendek menutup dua rapat panjang.
        Rapat[] ujiDurasi = {
            new Rapat("Rapat Satu", 8, 12),
            new Rapat("Rapat Singkat", 10, 13),
            new Rapat("Rapat Dua", 12, 16),
        };
        System.out.println("Data 2 (greedy durasi tersingkat):");
        pilih(ujiDurasi, Comparator.comparingInt(r -> r.selesai() - r.mulai()));
        System.out.println("Data 2 (greedy selesai terawal):");
        pilih(ujiDurasi, Comparator.comparingInt(Rapat::selesai));
    }

    // Greedy generik: urutkan sesuai strategi, ambil rapat yang tidak bertumpang tindih.
    static void pilih(Rapat[] jadwal, Comparator<Rapat> strategi) {
        Rapat[] urut = jadwal.clone();
        Arrays.sort(urut, strategi);

        List<Rapat> terpilih = new ArrayList<>();
        int selesaiTerakhir = Integer.MIN_VALUE;
        for (Rapat r : urut) {
            if (r.mulai() >= selesaiTerakhir) {
                terpilih.add(r);
                selesaiTerakhir = r.selesai();
            }
        }

        StringBuilder sb = new StringBuilder("  Terpilih: ");
        for (int i = 0; i < terpilih.size(); i++) {
            if (i > 0) {
                sb.append(", ");
            }
            Rapat r = terpilih.get(i);
            sb.append(r.nama()).append(" (").append(r.mulai()).append("-")
                    .append(r.selesai()).append(")");
        }
        System.out.println(sb);
        System.out.println("  Jumlah rapat: " + terpilih.size());
    }
}