Algoritma Greedy?

 Apa Itu Algoritma Greedy?

Algoritma Greedy, atau Algoritma Serakah, adalah salah satu pendekatan algoritmik yang paling sederhana dan intuitif. Prinsip utamanya adalah membuat pilihan terbaik pada setiap langkah saat itu juga, dengan harapan bahwa serangkaian pilihan lokal yang optimal akan menghasilkan solusi global yang optimal. Algoritma ini tidak mempertimbangkan konsekuensi dari setiap pilihan di masa depan, melainkan fokus pada apa yang paling menguntungkan saat itu.

Contoh: Masalah Penukaran Uang

Ini adalah contoh klasik yang paling baik untuk memahami Algoritma Greedy.

Masalah: Tukarkan sejumlah uang dengan koin sesedikit mungkin. Koin yang Tersedia: Rp 1.000, Rp 500, Rp 200, Rp 100, Rp 50, Rp 25.

Cara Kerja Algoritma:

1. Ambil koin dengan nominal terbesar yang bisa Anda gunakan.
2. Ulangi langkah 1 sampai sisa uang habis.

Contoh Kasus: Menukarkan uang sebesar Rp 1.275.

• Langkah 1: Ambil koin Rp 1.000 (terbesar). Sisa uang: Rp 275.
• Langkah 2: Ambil koin Rp 200 (terbesar yang tersisa). Sisa uang: Rp 75.
• Langkah 3: Ambil koin Rp 50. Sisa uang: Rp 25.
• Langkah 4: Ambil koin Rp 25. Sisa uang: Rp 0.

Hasil Akhir: 1 koin Rp 1.000, 1 koin Rp 200, 1 koin Rp 50, dan 1 koin Rp 25.

Diagram Alir dan Deskripsinya

Berikut adalah diagram alir yang memvisualisasikan langkah-langkah di atas, diikuti dengan deskripsi rinci dari setiap tahap.

Deskripsi Diagram Alir

Diagram alir di atas menggambarkan alur kerja algoritma secara rinci:

1. Mulai: Ini adalah titik awal dari algoritma, di mana program mulai dieksekusi.
2. Deklarasi Koin & Uang: Pada tahap ini, kita mendefinisikan daftar koin yang tersedia (diurutkan dari yang terbesar ke terkecil) dan jumlah uang yang akan ditukar.
3. Inisialisasi Hasil: Variabel untuk menyimpan hasil penukaran (misalnya, dalam bentuk kamus atau array) diatur menjadi kosong. Ini adalah tempat kita akan mencatat berapa banyak koin dari setiap nominal yang digunakan.
4. Untuk Setiap Koin: Algoritma memulai perulangan melalui daftar koin, dimulai dari koin dengan nilai tertinggi (dalam kasus ini, Rp 1.000).
5. Apakah Sisa Uang >= Koin?: Ini adalah inti dari "sifat serakah". Algoritma memeriksa apakah koin saat ini dapat digunakan untuk menukar sisa uang.
6. Ya: Jika koin bisa digunakan, algoritma melakukan tiga langkah:
• Hitung Jumlah Koin: Menghitung berapa banyak koin yang bisa diambil.
• Simpan Hasil: Menambahkan jumlah koin yang diambil ke variabel hasil.
• Kurangi Sisa Uang: Mengurangi jumlah uang yang akan ditukar dengan nilai koin yang baru saja diambil.
7. Tidak: Jika koin saat ini tidak bisa digunakan, algoritma akan melangkah ke koin berikutnya.
8. Selesai Perulangan: Perulangan berhenti setelah semua koin dipertimbangkan.
9. Tampilkan Hasil: Menampilkan jumlah koin yang digunakan untuk setiap nominal.
10. Selesai: Algoritma berakhir.

Melalui diagram ini, kita bisa melihat bahwa Algoritma Greedy berfokus pada pengambilan keputusan satu per satu, tanpa pernah melihat ke belakang. Ini membuat algoritma ini sangat efisien, meskipun tidak selalu memberikan solusi optimal untuk semua jenis masalah.