Pengertian Algoritma Greedy

Halo! Pernahkah Anda menerima uang kembalian dari warung? Di sinilah algoritma greedy bekerja. Saat kasir memberikan kembalian Rp13.000, ia biasanya mengambil pecahan terbesar yang mungkin, seperti Rp10.000, lalu Rp2.000, lalu Rp1.000. Proses sederhana ini ternyata adalah inti dari pengertian algoritma greedy: selalu pilih opsi terbaik saat ini tanpa menoleh ke belakang. Dalam panduan lengkap ini, kita akan membongkar prinsip, contoh kode siap pakai, serta kapan strategi rakus ini efektif dan kapan justru gagal. Jika Anda pernah bingung membedakan greedy dengan dynamic programming atau backtracking, artikel ini akan menjelaskannya dengan analogi sederhana dan studi kasus nyata agar tidak sekadar teori.

Apa Itu Algoritma Greedy?

Secara formal, algoritma greedy adalah strategi pemecahan masalah yang selalu membuat pilihan optimal di setiap tahap dengan asumsi bahwa pilihan lokal terbaik akan mengarah ke solusi global terbaik. Kata greedy berasal dari bahasa Inggris yang berarti rakus atau tamak, menggambarkan sifat algoritma yang selalu ingin mengambil yang terbaik di setiap kesempatan. Bayangkan Anda di prasmanan dan selalu mengambil lauk yang terlihat paling menggiurkan di setiap langkah tanpa memikirkan kombinasi akhir; itulah mentalitas greedy.

Menurut GeeksforGeeks, algoritma greedy merupakan paradigma yang memecahkan masalah dengan membuat pilihan lokal optimal dengan harapan menemukan solusi global optimal. Pendekatan ini cocok ketika pilihan lokal terbaik benar-benar mengarah pada solusi global terbaik. Tidak semua masalah memiliki sifat ini, sehingga penting memahami karakteristiknya sebelum menerapkan greedy secara membabi buta.

Beberapa karakteristik utama algoritma greedy meliputi:

• Greedy Choice Property — Pilihan lokal optimal di setiap langkah tidak memengaruhi pilihan sebelumnya. Keputusan yang sudah diambil bersifat final dan tidak perlu diubah.
• Optimal Substructure — Solusi optimal masalah besar dapat dibangun dari solusi optimal sub-masalah yang lebih kecil. Jika sub-masalah diselesaikan optimal, gabungannya juga optimal.
• Langkah demi langkah — Algoritma membangun solusi secara bertahap, satu keputusan pada satu waktu, tanpa melihat ke belakang atau melakukan backtrack.

Prinsip Kerja Algoritma Greedy

Meski terlihat sederhana, algoritma greedy mengikuti alur yang sistematis. Memahami alurnya membantu Anda merancang fungsi greedy yang tepat dan menghindari jebakan optimasi semu. Berikut langkah-langkahnya:

1. Identifikasi kandidat solusi — Tentukan semua kemungkinan pilihan yang tersedia di langkah saat ini.
2. Evaluasi setiap kandidat — Nilai setiap pilihan berdasarkan fungsi greedy atau fungsi objektif yang telah ditentukan.
3. Pilih yang terbaik — Ambil pilihan dengan nilai terbaik sesuai kriteria, misalnya nilai terbesar, biaya terkecil, atau waktu selesai paling awal.
4. Tandai sebagai sudah dipilih — Kunci pilihan tersebut agar tidak dipilih ulang di langkah berikutnya dan lanjutkan ke sisa kandidat.
5. Ulangi — Kembali ke langkah pertama sampai masalah selesai atau semua kandidat habis dievaluasi.

Kunci dari algoritma greedy ada pada langkah kedua: evaluasi hanya berdasarkan kondisi saat ini tanpa memprediksi dampak di masa depan. Inilah yang membuatnya sangat cepat, sering kali hanya O(n log n) karena didominasi pengurutan, namun juga menjadi kelemahannya ketika keputusan lokal ternyata menjebak solusi global.

Persoalan Optimasi dan Algoritma Greedy

Algoritma greedy banyak digunakan untuk persoalan optimasi, yaitu masalah yang menuntut pencarian solusi terbaik, baik maksimal maupun minimal. Dalam optimasi, ada dua komponen utama yang harus Anda kenali. Pertama, kendala (constraints) adalah batasan yang harus dipenuhi solusi, seperti kapasitas tas atau jadwal yang tidak boleh tumpang tindih. Kedua, fungsi objektif adalah besaran yang ingin dimaksimalkan atau diminimalkan, misalnya total keuntungan atau total biaya.

• Kendala (constraints) — Syarat yang membatasi ruang solusi. Contoh: total berat tidak boleh melebihi kapasitas knapsack.
• Fungsi objektif — Nilai yang dioptimalkan. Contoh: memaksimalkan nilai barang bawaan atau meminimalkan jumlah koin.

Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution), sedangkan solusi layak yang mengoptimumkan fungsi objektif disebut solusi optimal. Ada dua jenis optimasi utama:

• Maksimasi — Mencari nilai terbesar, misalnya keuntungan maksimal dari pemilihan investasi atau jumlah aktivitas terbanyak.
• Minimasi — Mencari nilai terkecil, misalnya biaya termurah atau waktu tempuh tersingkat.

Contoh 1: Masalah Pecahan Koin (Coin Change)

Masalah klasik untuk memahami algoritma greedy adalah menentukan jumlah koin paling sedikit untuk membayar nominal tertentu. Misalkan kasir memiliki koin Rp10.000, Rp5.000, Rp2.000, dan Rp1.000. Untuk membayar Rp13.000, strategi greedy mengambil koin terbesar yang masih muat, lalu mengulanginya. Hasilnya adalah Rp10.000 + Rp2.000 + Rp1.000, hanya tiga lembar.

function greedyCoinChange(total, denominations) {
 let remaining = total;
 let coins = [];
 for (let coin of denominations) {
 while (remaining >= coin) {
 remaining -= coin;
 coins.push(coin);
 }
 }
 return coins;
}
const denominations = [10000, 5000, 2000, 1000];
console.log(greedyCoinChange(13000, denominations)); // [10000, 2000, 1000]

Kode di atas memulai dari denominasi terbesar dan terus menggunakannya selama masih mencukupi sisa pembayaran. Langkah ini diulang sampai seluruh nominal terbayar. Untuk sistem koin kanonik seperti rupiah, greedy menghasilkan solusi optimal. Namun untuk denominasi aneh seperti [4,3,1] dan total 6, greedy akan memilih 4+1+1 (tiga koin) padahal optimal adalah 3+3 (dua koin).

Contoh 2: Activity Selection Problem

Bayangkan Anda memiliki beberapa aktivitas dengan waktu mulai dan selesai yang berbeda. Tujuannya memilih sebanyak mungkin aktivitas tanpa ada yang tumpang tindih. Strategi greedy yang terbukti optimal adalah selalu pilih aktivitas yang selesai paling awal, karena menyisakan ruang terbanyak untuk aktivitas selanjutnya. Ini seperti menyusun jadwal rapat: pilih rapat yang cepat selesai dulu agar slot kosong lebih banyak.

function activitySelection(activities) {
 // activities = [{name, start, finish},...]
 activities.sort((a, b) => a.finish - b.finish);
 let selected = [activities[0]];
 let lastFinish = activities[0].finish;
 for (let i = 1; i < activities.length; i++) {
 if (activities[i].start >= lastFinish) {
 selected.push(activities[i]);
 lastFinish = activities[i].finish;
 }
 }
 return selected;
}
const activities = [
 {name: 'A', start: 1, finish: 4},
 {name: 'B', start: 3, finish: 5},
 {name: 'D', start: 5, finish: 7}
];
console.log(activitySelection(activities)); // A dan D terpilih

Algoritma mengurutkan aktivitas berdasarkan waktu selesai, lalu iterasi sambil memeriksa apakah aktivitas berikutnya dimulai setelah aktivitas terakhir yang terpilih selesai. Jika ya, aktivitas tersebut diambil. Kesederhanaan ini membuat activity selection menjadi contoh favorit untuk mengajarkan greedy choice property yang benar-benar mengarah ke solusi global optimal.

Contoh 3: Fractional Knapsack

Berbeda dengan 0/1 Knapsack yang tidak bisa diselesaikan optimal dengan greedy, versi fraksional memungkinkan kita mengambil sebagian item. Strateginya adalah pilih item dengan rasio nilai per bobot tertinggi terlebih dahulu, mirip memilih camilan dengan rasa paling enak per gram saat ransel hampir penuh. Jika kapasitas tidak cukup untuk satu item utuh, ambil sebagian yang masih muat.

function fractionalKnapsack(capacity, items) {
 // items = [{name, weight, value},...]
 items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
 let totalValue = 0;
 let taken = [];
 for (let item of items) {
 if (capacity >= item.weight) {
 capacity -= item.weight;
 totalValue += item.value;
 taken.push({name: item.name, fraction: 1});
 } else {
 const fraction = capacity / item.weight;
 totalValue += item.value * fraction;
 taken.push({name: item.name, fraction});
 break;
 }
 }
 return { totalValue, taken };
}
// Contoh: kapasitas 50, item A(10,60), B(20,100), C(30,120)
// Rasio: A 6, B 5, C 4 -> ambil A penuh, B penuh, C sebagian

Pengurutan berdasarkan rasio value per weight adalah kunci. Setelah itu, algoritma mengambil item satu per satu sampai kapasitas habis. Jika item terakhir tidak muat penuh, ia diambil secara fraksional dan loop berhenti. Untuk kasus fraksional, greedy terbukti optimal dan jauh lebih cepat daripada dynamic programming yang dibutuhkan versi 0/1.

Kapan Algoritma Greedy Efektif?

Tidak semua masalah bisa diselesaikan dengan algoritma greedy. Greedy memberikan hasil optimal hanya ketika masalah memiliki dua properti kunci berikut. Jika salah satu tidak terpenuhi, greedy mungkin menghasilkan solusi yang terlihat bagus tetapi sebenarnya bukan yang terbaik.

1. Greedy Choice Property — Pilihan lokal optimal benar-benar mengarah ke solusi global optimal. Contoh paling jelas adalah activity selection: memilih yang selesai paling awal selalu mengarah ke jumlah aktivitas maksimal.
2. Optimal Substructure — Solusi optimal dari sub-masalah dapat digabungkan menjadi solusi optimal masalah utama. Jika sub-masalah diselesaikan optimal, gabungannya juga optimal.

Contoh masalah yang bisa diselesaikan dengan benar oleh algoritma greedy meliputi:

• Minimalisasi jumlah koin atau lembaran uang pada sistem kanonik
• Pemilihan aktivitas tanpa tumpang tindih
• Fractional Knapsack
• Huffman Coding untuk kompresi optimal
• Kruskal dan Prim untuk Minimum Spanning Tree
• Dijkstra untuk jarak terpendek dari satu sumber

Kapan Algoritma Greedy Gagal?

Tidak semua persoalan optimasi cocok dengan pendekatan rakus. Ketika greedy choice property tidak terpenuhi, keputusan lokal terbaik justru menjebak solusi global. Mengenali kapan greedy gagal sama pentingnya dengan mengetahui kapan ia berhasil, agar Anda tidak salah memilih alat.

• 0/1 Knapsack Problem — Ketika item tidak bisa dipecah, greedy sering gagal. Solusi optimal membutuhkan dynamic programming untuk mempertimbangkan kombinasi item secara menyeluruh.
• Travelling Salesman Problem (TSP) — Mencari rute terpendek yang mengunjungi semua kota sekali lalu kembali ke awal. Greedy yang selalu pilih kota terdekat berikutnya sering menghasilkan tur yang jauh dari optimal.
• Longest Path Problem — Mencari jalur terpanjang dalam graf berbobot. Pilihan lokal terbaik tidak menjamin jalur terpanjang global.

Kegagalan ini bukan kekurangan greedy, melainkan cerminan bahwa masalah tersebut memang membutuhkan paradigma lain. Jika Anda menemui masalah di mana pilihan lokal memengaruhi ketersediaan pilihan masa depan secara kompleks, curigai bahwa greedy bukan jawabannya.

Perbandingan: Greedy vs Dynamic Programming vs Backtracking

Memahami perbedaan tiga paradigma populer membantu Anda memilih pendekatan yang tepat untuk setiap masalah. Tabel berikut merangkum perbandingannya secara ringkas.

Greedy unggul dalam kecepatan ketika propertinya terpenuhi, dynamic programming unggul dalam optimalitas untuk masalah dengan sub-masalah tumpang tindih, sedangkan backtracking menjamin kebenaran dengan mengorbankan performa. Sebagai pembelajar, latih intuisi dengan mencoba satu masalah menggunakan ketiga pendekatan dan bandingkan hasilnya.

Kelebihan dan Kekurangan Algoritma Greedy

Kelebihan

• Implementasi relatif sederhana dan mudah dipahami, cocok untuk pemula.
• Kompleksitas waktu rendah dibandingkan backtracking, sehingga efisien untuk data besar.
• Sangat efisien untuk masalah yang memang memiliki greedy choice property.
• Mudah dioptimasi dan di-debug karena alurnya linear tanpa rekursi kompleks.

Kekurangan

• Tidak selalu menghasilkan solusi optimal untuk semua jenis masalah.
• Sulit membuktikan apakah pilihan greedy benar-benar optimal tanpa analisis matematis mendalam.
• Satu kali keputusan diambil, tidak bisa diubah karena tidak ada mekanisme backtrack.

Tips Menguasai Algoritma Greedy

1. Pahami properti greedy choice dan optimal substructure sebelum menerapkan. Pastikan masalah memiliki kedua properti ini melalui pembuktian atau referensi.
2. Mulai dari masalah sederhana seperti coin change, activity selection, dan fractional knapsack untuk membangun intuisi.
3. Bandingkan dengan pendekatan lain dengan menyelesaikan masalah yang sama menggunakan dynamic programming untuk melihat perbedaan hasil dan performa.
4. Analisis kasus boundary dengan menguji algoritma pada data minimal, data terurut, dan data acak untuk memastikan ketahanan.
5. Latihan di platform kompetitif seperti LeetCode, HackerRank, dan Codeforces yang menyediakan banyak soal greedy dengan tingkat kesulitan bertahap.

Rangkuman Algoritma Greedy

Pemahaman tentang algoritma greedy merupakan bekal fundamental bagi setiap programmer dan ilmuwan komputer. Meskipun sederhana dari sisi implementasi, pemilihan fungsi greedy yang tepat dan membuktikan bahwa pilihan tersebut menghasilkan solusi optimal membutuhkan pemahaman konsep yang kuat. Mulailah dengan masalah klasik seperti koin dan aktivitas, latih intuisi Anda, dan perlahan tingkatkan ke Huffman atau Dijkstra. Dengan kombinasi teori dan praktik, Anda akan mampu menentukan kapan algoritma greedy menjadi alat yang tepat. Untuk pendalaman lebih lanjut, baca panduan di GeeksforGeeks Greedy Algorithms dan jelajahi artikel pengertian algoritma serta kategori programming di InfanThree. Semangat berlatih dan sampai jumpa di pembahasan algoritma selanjutnya!

Hal yang sering ditanyakan seputar Pengertian Algoritma Greedy