Algoritma Greedy

 Pernah nggak sih kamu main game dan harus cepat memutuskan langkah mana yang paling menguntungkan? Nah, tanpa sadar kamu sedang berpikir greedy! 

Dalam dunia algoritma, logika greedy juga bekerja seperti itu : memilih keputusan terbaik di setiap langkah untuk mencapai hasil yang optimal.

Meski sederhana, pendekatan ini sering menjadi kunci efisiensi dalam berbagai permasalahan kompleks. Mari kita pelajari bagaimana logika greedy bekerja dan kapan ia bisa digunakan dengan bijak.

Greedy adalah metode pemecahan masalah dengan selalu memilih pilihan terbaik yang terlihat saat ini, tanpa memikirkan dampak ke depan.

Cara ini cepat dan sederhana, tetapi tidak selalu menjamin hasil yang paling optimal untuk semua jenis masalah.

Contoh dalam kehidupan nyata :

1: Menghitung Uang Kembalian (Masalah Koin)

Misalnya kamu harus mengembalikan uang Rp7.000 dengan pecahan Rp5.000, Rp2.000, dan Rp1.000.

Cara greedy akan berpikir seperti ini:

Ambil dulu pecahan terbesar yang mungkin → ambil Rp5.000

Sisa Rp2.000 → ambil Rp2.000

Selesai, total dua lembar uang.

Hasil: cepat dan efisien, karena memilih nilai terbesar dulu di setiap langkah.

2: Mengatur Waktu Belajar

Kamu punya 2 jam untuk belajar 3 mata pelajaran: TIK (butuh 30 menit), Matematika (1 jam), dan Bahasa Inggris (45 menit).

Tujuanmu: memaksimalkan jumlah mata pelajaran yang bisa selesai dalam 2 jam.

Logika greedy akan:

Pilih pelajaran dengan waktu paling singkat dulu → TIK (30 menit).

Lanjut ke Bahasa Inggris (45 menit).

Total waktu 75 menit, masih sisa 45 menit → cukup untuk sebagian Matematika.

Hasilnya: kamu menyelesaikan lebih banyak topik dalam waktu terbatas.

Berikut beberapa contoh game yang bisa digunakan untuk menjelaskan algoritma Greedy 

1. Game Pengambilan Koin (Coin Change Game)

Deskripsi:

• Pemain harus mengumpulkan jumlah uang tertentu (misalnya Rp 6.000)

• Disediakan koin dengan nilai: 5.000, 2.000, 1.000

• Tujuannya: ambil jumlah koin paling sedikit untuk mencapai total tersebut.

• Pemain punya tas dengan kapasitas 10 kg.

• Ada beberapa barang dengan berat dan nilai berbeda.

• Ada beberapa anak, masing-masing bisa diberi permen dalam waktu tertentu.

• Tujuan: bagikan permen ke sebanyak mungkin anak tanpa tumpang tindih waktu.

• Selalu pilih anak dengan waktu selesai paling cepat terlebih dahulu.

• Ini sama seperti Activity Selection Problem.

Logika Greedy:

Selalu pilih koin terbesar yang masih bisa digunakan.

Contoh:

Target = 6.000

→ Ambil 5.000 (sisa 1.000)

→ Ambil 1.000

Total 2 koin (pilihan terbaik lokal).

2. Game Tas Harta (Knapsack Problem)

Deskripsi:

Contoh:

Barang Berat Nilai

Emas 5 kg 100

Perak 3 kg 60

Permata 2 kg 40

Tujuan:

Isi tas agar nilai total terbesar, tapi tidak melebihi kapasitas.

Logika Greedy:

Pilih barang berdasarkan nilai per berat tertinggi → ambil yang paling “efisien”.

Permata (40/2 = 20)

Perak (60/3 = 20)

Emas (100/5 = 20)

Karena sama, bisa ambil urutan apa pun sampai penuh.

3. Game Jalur Terpendek (Shortest Path Game)

Deskripsi:

Pemain harus mencari jalan tercepat dari titik A ke B di peta (seperti game labirin).

Setiap jalan punya waktu/tempuh tertentu.

Logika Greedy:

Selalu pilih jalur dengan waktu tempuh terkecil dari posisi saat ini (contoh algoritma Dijkstra → berbasis greedy).

Contoh sederhana bisa dibuat di kertas atau game simulasi peta.

Algoritma Greedy cocok untuk game yang:

• Punya banyak pilihan keputusan,

• Tapi tiap langkah harus memilih “yang terbaik saat itu”,

• Tanpa meninjau hasil akhir secara keseluruhan.

Ingin mencoba game dengan algoritma greedy? Silahkan klik tombol ini :