Penukaran Uang

    1.      Kasus Penukaran Uang : Diberikan uang senilai A = 8 $. Tukar A dengan koin-koin uang yang             tersedia banyak koin 1 $, 3 $, 5 $. Berapa jumlah minimum koin yang diperlukan untuk penukaran      tersebut?

 Penyelesaian :

·         Persoalan Optimasi

8 = 1+1+1+1+1+1+1+1 (8 koin)

8 = 1+1+1+5  (4 Koin)

8 = 1+1+3+3 (4 koin)

8 = 5+3  (2 koin)

Banyak koin minimum yang dapat ditukar untuk menghasilkan 8 $ adalah :

Minimum : 1 koin 5$, 1 koin 3$

Jadi : solusi optimal 2 koin

·         Exhaustive –Search

Untuk mencari kompleksitas hitung jumlah koin dengan nilai yang berbeda,

Misal :

1+1+1+1+1+1+1+1 = 8  ( jumlah nilai koin berbeda ada 1)

1+1+1+5 = ( jumlah nilai koin berbeda ada 2 )

3+5 = 8  ( jumlah nilai koin berbeda ada 2 )

Maka : pilih jumlah nilai koin yang berbedanya paling sedikit. 

Jadi di dapat 2 buah koin.

Untuk 2 buah koin terdapat berapa kemungkinan . . . ?

Misal : 1 buah koin terdapat angka dan gambar.

Maka kemungkinan yang bisa terjadi adalah :

{A,A} {A,G} {G,G} {G,A}

Untuk 2 koin ada --> 4    kemungkinan

Untuk 3 koin ada --> 8 kemungkinan

Untuk  n  koin ada à  2ⁿ  kemungkinan

Untuk mengevaluasi setiap kemungkinan dibutuhkan n eksekusi.

Maka, kompleksitas : n * 2ⁿ

                      Pseudo-code Penukaran Uang

                Referensi :

•         http://topaninfo.blogspot.co.id/2012/12/Algoritma-GREEDY-Definisi-Contoh-Program.html
•         https://www.it-jurnal.com/pengertian-algoritma-greedy/
•         https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html#algoritma-greedy
•         http://kurniadi-addi.blogspot.co.id/2015/07/materi-analisis-algortima-algoritma.html