Penerapan Algoritma Greedy

Sinopsis

Dunia teknik optimasi mempunyai banyak jurus ampuh untuk menangani masalah optimasi minimisasi / maksimisasi. Salah satu nya yaitu algoritma greedy (RAKUS) yang merupakan metode yang paling populer. Contoh persoalan optimasi yaitu Masalah Penukaran Uang: Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?

Contoh 1

Tersedia pecahan koin dengan nilai 1, 5, 10, 25; Maka uang senilai 32 dapat ditukar dengan banyak cara berikut:

• 32 = 1 + 1 + … + 1 (32 koin)
• 32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin)
• 32 = 10 + 10 + 10 + 1 + 1 (5 koin)

Dari beberapa cara diatas didapakan Minimum: 32 = 25 + 5 + 1 + 1 (4 koin)

Contoh 2

Kita coba menggunakan algoritma Greedy untuk memecahkan persoalan minimum. Tersedia pecahan uang koin dengan nilai 12,10,5,1. Berapa jumlah koin (minimal) yang dibutuhkan untuk ditukar dengan uang senilai 30? Algoritma Greedy melalui langkah-langkah berikut ini

1. Urutkan tiap anggota mulai besar – terkecil: 12;10;5;1
2. Jumlah tiap anggota secara kumulatif, pastikan jumlah kumulatif tiap anggota tidak lebih dari target seperti berikut bila menggunakan tabel.

Pada anggota ke 2, mengapa anggota 2 yaitu 10 bernilai 0?

1. Anggota 1 = [12+12] = 24
2. Anggota 2 = 24 + [10] = 34 (TIDAK BISA karena 34 > 30) sehingga Anggota 2 = TIDAK BISA diikutkan
3. Anggota 3 = 24 + [5+5] = 34 (TIDAK BISA karena 34 > 30) sehingga Anggota 3 = 24 + [5] = 29
4. Anggota 4 = 29 + [1]

Sehingga bisa disimpulkan menjadi
Ada 2 koin untuk 12 = 24
Ada 1 koin untuk 5 =5
Ada 1 koin unuk 1=1
Total 24+5+1 = 30
Maka jumlah koin ada 4. Dengan kata lain: algoritma greedy melibatkan pencarian sebuah himpunan bagian, S, dari himpunan kandidat, C; yang dalam hal ini, S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimisasi oleh fungsi obyektif.

Tapi ada catatan tersendiri lho untuk kasus diatas: akan lebih ringkas menggunakan 3 koin bila digunakan pecahan 10 saja.

Contoh 3

Tersedia pecahan koin 5, 4, 3, dan 1. Berapa jumlah koin yang dibutukan untuk ditukar dengan nilai 7 ?

1. Solusi greedy: 7 = 5 + 1 + 1 ( 3 koin) ? tidak optimal
2. Solusi optimal: 7 = 4 + 3 ( 2 koin)

Jika jawaban terbaik mutlak TIDAK diperlukan, maka algoritma greedy sering berguna untuk menghasilkan solusi hampiran (approximation), daripada menggunakan algoritma yang lebih rumit untuk menghasilkan solusi yang eksak. Bila algoritma greedy optimum, maka keoptimalannya itu dapat dibuktikan secara matematis.

Optimasi Algoritma Greedy

Algoritma Greedy sejatinya dapat dioptimalkan! Yaitu dengan cara mengurangi satu demi satu anggota koin, dan melakukan teknik Greedy, lihat kondisi berikut untuk setiap anggota koin yang di remove satu persatu!

Contoh soal: Tersedia nilai koin 5;4;3;1 dengan target untuk ditukar nilai 7?
Perhatikan tabel dibawah ini, dengan cara membandingkan tiap ulangan, maka akan didapatkan solusi optimal.

Maka dapat dibandingkan antara tiap ulangan untuk mencari nilai terkecil. Penulis menggunakan java untuk mempermudah algoritma diatas karena terlalu banyak iterasi sehingga perlu dibuat dengan bahasa pemrograman daripada dihitung menggunakan excel

Berikut adalah contoh kasus lainnya

Contoh 4

Nominal Koin yang tersedia: 10, 7, 1. Uang yang ditukar: 15?

1. Solusi greedy: 15 = 10 + 1 + 1 + 1 + 1 + 1 (6 koin)
2. Solusi optimal: 15 = 7 + 7 + 1 (hanya 3 koin)

Contoh 5

Nominal Koin yang tersedia: 15, 10, dan 1. Uang yang ditukar: 20?

1. Solusi greedy: 20 = 15 + 1 + 1 + 1 + 1 + 1 (6 koin)
2. Solusi optimal: 20 = 10 + 10 (2 koin)

Ternyata Algoritma Greedy AKAN TETAP OPTIMAL dengan teknik diatas!  Berikut adalah Contoh 2 yang diatas, ternyata greedy bisa dioptimasikan lagi dengan teknik iterasi per anggota

Kalian bisa mendapatkan source code nya dengan cara subcribe dan follow blog ini