Algoritma Greedy pert 1

Kalau kamu sudah belajar algoritma dasar, pasti bakal ketemu satu strategi yang dipakai di banyak tugas pemrograman dan masalah matematika: Algoritma Greedy. Dari namanya aja sudah unik—“greedy” artinya “rakus”. Tapi tenang, ini rakus yang positif kok! Greedy di algoritma bukan berarti serakah yang jelek, tapi mengambil pilihan terbaik di setiap langkah tanpa mikir panjang.

 

• cari rute tercepat
• ambil uang kembalian paling efisien
• optimasi biaya
• penjadwalan
• pemilihan solusi minimum

Yuk kita bahas dengan gaya santai, tapi tetap lengkap biar makin paham!

---

1. Apa Itu Algoritma Greedy?

Algoritma Greedy adalah strategi penyelesaian masalah dengan cara selalu memilih keputusan terbaik yang terlihat pada saat itu. Tanpa mundur, tanpa revisi, tanpa mikir jauh ke masa depan.

Pilih sekarang, yang paling menguntungkan, terus lanjutkan sampai selesai. Itulah konsep greedy.

Karena tiap langkah langsung ambil yang terlihat paling optimal, greedy jadi algoritma yang:

• cepat
• mudah dipahami
• tidak banyak hitungan rumit
• cocok untuk masalah besar

Tapi konsekuensinya: hasil greedy tidak selalu memberikan solusi paling optimal. Untuk beberapa masalah cocok, tapi untuk beberapa masalah lainnya justru gagal. Makanya, sebelum memakai greedy, kita harus paham jenis masalahnya.

---

2. Kenapa Disebut “Greedy”?

Karena sifat algoritmanya mirip orang lagi milih sesuatu secara spontan: ambil yang paling bagus saat ini tanpa mikir jangka panjang.

Contoh sederhana:

Kamu dikasih beberapa koin lalu disuruh ambil uang senilai Rp 6.000 dengan jumlah koin paling sedikit. Kebanyakan orang (dan greedy) pasti akan ambil koin yang paling besar dulu:

• ambil koin 5000 (1 koin)
• ambil koin 1000 (1 koin)

Total: 2 koin. Itu strategi greedy.

Gampang dan cepat kan? Nah, begitulah cara greedy bekerja.

---

3. Sifat Utama Algoritma Greedy

Ada dua ciri yang bikin masalah cocok untuk diselesaikan dengan greedy:

1. Greedy-Choice Property

Solusi optimal dapat dicapai dengan membuat keputusan terbaik pada langkah awal. Artinya, pilihan paling menguntungkan saat ini berkontribusi menuju solusi global terbaik.

2. Optimal Substructure

Masalah besar bisa dipecah menjadi masalah kecil, dan solusi optimal bagian kecil membentuk solusi optimal keseluruhan.

Kalau dua sifat ini ada → cocok banget pakai greedy. Kalau tidak ada? Wah, greedy biasanya gagal total.

---

4. Cara Kerja Algoritma Greedy

Secara umum, algoritma greedy punya pola seperti ini:

1. Tentukan himpunan pilihan
2. Tentukan fungsi untuk memilih pilihan terbaik
3. Ambil pilihan terbaik (secara lokal)
4. Tambahkan ke solusi
5. Ubah kondisi masalah
6. Ulangi sampai masalah selesai

Kuncinya ada di langkah nomor 3: memilih yang paling menguntungkan sekarang.

---

5. Contoh Nyata dalam Kehidupan Sehari-Hari

1. Kasir ingin memberi kembalian tercepat

Kasir biasanya pakai strategi greedy: ambil pecahan uang paling besar dulu, baru pecahan kecil.

2. Google Maps mencari rute tercepat

Algoritma tertentu memperkirakan waktu paling cepat berdasarkan kondisi real-time. Memilih jalur tercepat saat ini adalah sifat greedy.

3. Membeli barang dengan promo maksimum

Kalau ada promo “diskon terbesar”, kita otomatis cari barang yang paling menguntungkan dulu. Itu juga greedy.

---

6. Contoh Kasus 1: Pengambilan Koin (Coin Change)

Ini contoh klasik greedy: membuat jumlah tertentu menggunakan jumlah koin paling sedikit.

Kasus:

Uang yang ingin dibentuk: Rp 6.000

Pecahan tersedia: 5000, 2000, 1000

Strategi Greedy:

• ambil 5000 → sisa 1000
• ambil 1000 → sisa 0

Total koin: 2 (optimal)

Greedy berhasil.

Pseudocode:

START
nilai = 6000
pecahan = [5000, 2000, 1000]
total_koin = 0

FOR p in pecahan:
    WHILE nilai >= p:
        nilai = nilai - p
        total_koin = total_koin + 1
END FOR

PRINT total_koin
END

---

Contoh Kasus di Mana Greedy Gagal

Misalnya pecahan koin: 4, 3, 1 Nilai yang ingin dibentuk: 6

Pilihan Greedy:

• ambil 4 → sisa 2
• ambil 1 → sisa 1
• ambil 1 → sisa 0

Total = 3 koin

Padahal solusi optimal:

• 3 + 3 = 2 koin

Nah, ini contoh bahwa greedy tidak selalu optimal.

---

7. Contoh Kasus 2: Fractional Knapsack (Tas Pecahan)

Ini contoh greedy paling terkenal: memilih barang untuk dimasukkan ke tas dengan kapasitas tertentu agar nilai keuntungan maksimal.

Tapi versi yang bisa diselesaikan greedy adalah fractional, di mana kita boleh mengambil barang sebagian.

Kasus:

Kapasitas tas: 50 kg

Barang:

• A: berat 10, nilai 60
• B: berat 20, nilai 100
• C: berat 30, nilai 120

Strategi Greedy:

Pilih berdasarkan “nilai per berat” (value/weight)

• A = 6
• B = 5
• C = 4

Urutan pengambilan:

• ambil A (penuh)
• ambil B (penuh)
• ambil sebagian C

Masih banyak ruang? Ambil sebagian C.

---

8. Contoh Kasus 3: Penjadwalan Kegiatan (Activity Selection)

Masalah: memilih kegiatan terbanyak tanpa bentrok jadwal.

Greedy: pilih kegiatan yang selesai paling cepat.

Contoh jadwal:

A: 1 - 4
B: 3 - 5
C: 0 - 6
D: 5 - 7
E: 8 - 9

Greedy memilih:

• A
• D
• E

Total: 3 kegiatan Dan itu solusi optimal.

---

9. Kapan Greedy Cocok Dipakai?

Cocok kalau:

• Masalah punya greedy-choice property
• Masalah punya optimal substructure
• Keputusan lokal memberi dampak global positif
• Tujuan: cepat, efisien, dan mudah

Tidak cocok kalau:

• Butuh perhitungan menyeluruh
• Perlu backtracking
• Masalah kompleks seperti knapsack 0/1

---

10. Kelebihan dan Kekurangan Greedy

Kelebihan:

• super cepat
• mudah dipahami
• implementasi sederhana
• dapat menyelesaikan banyak masalah harian

Kekurangan:

• tidak selalu optimal
• kadang salah total pada kasus tertentu
• harus dipastikan dulu apakah cocok

---

11. Pseudocode Umum Algoritma Greedy

START
Inisialisasi solusi kosong
WHILE masih ada pilihan:
    pilih opsi terbaik
    masukkan dalam solusi
    perbarui kondisi
END WHILE
Output solusi
END

---

Andi Bronnanjar

Kualitas makhluk berdasarkan seberapa manfaat untuk sesama maupun lingkungan alam sekitar.

Bagikan Artikel ini