2. Algoritma Greedy
Greedy secara harfiah berarti rakus atau tamak. Meskipun dalam pengertian sehari-hari, kata “rakus” dan “tamak” memiliki konotasi negatif, namun dalam konteks Informatika, kita mengartikan greedy dalam konteks sebagai sebuah strategi penyelesaian masalah yang dapat berguna dalam merancang sebuah algoritma atau solusi bagi sebuah permasalahan komputasional. Oleh karena itu, diharapkan tidak ada konotasi negatif pada kata greedy dalam konteks ini.
Teknik greedy adalah salah satu teknik penyelesaian masalah yang biasa digunakan untuk menyelesaikan permasalahan optimasi. Permasalahan optimasi berarti kita ingin menghitung sebuah hasil yang terbaik dari sebuah proses tertentu. Terbaik disini dapat berarti nilai yang paling kecil ataupun paling besar, tergantung dari jenis permasalahannya. Dalam menyelesaikan permasalahan optimasi seperti ini, algoritma greedy akan menerapkan prinsip “mengambil serangkaian langkah terbaik pada setiap saat”.
Contoh 1: Membawa Ikan 1
Budi ingin membawa beberapa ekor ikan yang sudah tersimpan dalam kantong-kantong plastik untuk diangkut di dalam mobilnya. Terdapat 8 buah kantong dengan yang berisi masing-masing 3, 5, 2, 8, 4, 6, 6, dan 3 ekor ikan. Namun sayangnya, mobilnya hanya mampu membawah 4 buah kantong. Kantong-kantong manakah yang harus dibawa oleh Budi agar jumlah ikan yang dibawanya sebanyak mungkin?
Jawab:
Untuk dapat membawa sebanyak mungkin ikan, Budi harus memilih kantong-kantong dengan sebanyak mungkin ikan. Oleh karena itu, algoritma greedy dapat diterapkan disini, dengan cara kita mengambil kantong mulai dari yang berisi ikan paling banyak terlebih dahulu, sampai didapatkan 4 buah kantong. Dengan demikian, kita harus mengurutkan kantong-kantong terlebih dahulu mulai dari yang paling banyak ikannya, sampai dengan yang paling sedikit, sehingga urutannya menjadi: 8, 6, 6, 5, 4, 3, 3, 2.
Jika kita ambil 4 buah kantong pertama, maka total banyaknya ikan yang dapat dibawa adalah 8 + 6 + 6 + 5 = 25 ekor ikan. Tentunya tidak ada pilihan 4 kantong yang akan menghasilkan total banyaknya ikan lebih dari 25 ekor.
Contoh 2: Membayar dengan Uang Kembalian
Misalnya, Andi membeli sebuah buku seharga Rp37.000. Ia membayar dengan uang Rp50.000, sehingga kasir harus memberikan kembalian sebesar Rp13.000.
Kasir memiliki pecahan uang Rp10.000, Rp5.000, Rp2.000, Rp1.000, dan Rp500. Bagaimana cara kasir memberikan kembalian dengan jumlah lembar uang sesedikit mungkin?
Jawab:
Untuk mendapatkan jumlah lembar uang sesedikit mungkin, kasir dapat menggunakan algoritma greedy, yaitu memilih pecahan uang terbesar yang masih dapat digunakan pada setiap langkah.
Kembalian yang harus diberikan adalah Rp13.000. Pertama, kasir memilih uang pecahan Rp10.000, sehingga sisa kembalian menjadi Rp3.000. Selanjutnya, kasir memilih uang pecahan Rp2.000, sehingga tersisa Rp1.000. Terakhir, kasir memilih uang pecahan Rp1.000.
Dengan demikian, kembalian Rp13.000 dapat diberikan menggunakan:
Rp10.000 + Rp2.000 + Rp1.000 = Rp13.000
Jadi, kasir hanya membutuhkan 3 lembar uang.