ALGORITMA GREEDY UNTUK PENYELESAIN PERSOALAN UANG KOIN

ALGORITMA GREEDY UNTUK PENYELESAIN PERSOALAN UANG KOIN

Ilham Maulana

Jurusan Teknik Informatika, STMIK Bani Saleh Bekasi

Jl. M. Hasibuan No.68 Bekasi Timur 17113

Email: caam190493@gmail.com

ABSTRAK

Dalam menghasilkan pemrograman untuk suatu rancangan perangkat lunak, dapat dihasilkan dengan berbagai strategi algoritma. Banyaknya algoritma yang dapat digunakan tersebut menimbulkan suatu pertanyaan yaitu algoritma manakah yang paling baik untuk menyelesaikan masalah tersebut. Algoritma greedy  salah satu yang dapat  memecahkan masalah selangkah demi selangkah. Setiap langkah memalsukan pilihan terbaik tanpa mempertimbangkan konsekuensi masa depan ("ambil apa yang bisa Anda dapatkan sekarang!"), Pada makalah ini akan dibahas bagaimana  algoritma dalam menyelesaikan persoalan uang koin dengan menggunakan algoritma greedy.  Selain itu juga dibahas bagaimana algoritma tersebut pada program sederhana yang dapat mengatasi persoalan penukaran uang koin dalam bahasa C++.Perubahan uang koin adalah masalah umum yang melibatkan prinsip algoritma serakah dalam kehidupan kita sehari-hari.

Kata Kunci : Algoritma, Greedy, Pemograman C++.

PENDAHULUAN

Algoritma adalah urutan langkah-langkah dalam memecahkan suatu masalah. Dalam melakukan pemrograman untuk mengimplementasikan suatu rancangan perangkat lunak, dapat ditempuh dengan berbagai strategi algoritma. Strategi Algoritma merupakan kumpulan metode atau teknik untuk memecahkan masalah guna mencapai tujuan yang ditentukan, yang dalam hal ini deskripsi metode atau teknik tersebut dinyatakan dalam suatu urutan langkah-langkah penyelesaian.

Secara umum, strategi pemecahan masalah dapat dikelompokan sebagai berikut:

1. Strategi solusi langsung (direct solution strategies)

a. Algoritma Brute force

b. Algoritma Greedy

2. Strategi berbasis pencarian pada ruang status

(state-space base strategies)

a. Algoritma Backtracking

b. Algoritma Branch and Bound

3. Strategi solusi atas-bawah (top-down solution strategies)

a.       Algoritma Divide and Conquer.

Di dalam sebuah algoritma terdapat bermacam jenis

operasi:

- Operasi baca/tulis,

- Operasi aritmetika (+, -, *, /)

- Operasi pengisian nilai (assignment)

- Operasi pengaksesan elemen larik

- Operasi pemanggilan fungsi/prosedur

- dll

DASAR TEORI

A. Algoritma Greedy

Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah. Pada setiap langkah tersebut akan dipilih keputusan yang paling optimal. Keputusan tersebut tidak perlu memperhatikan keputusan selanjutnya yang akan diambil, dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya.

a. Prinsip Utama Algoritma Greedy

Prinsip utama algoritma greedy adalah ?take what you can get now!?. Maksud dari prinsip tersebut adalah sebagai berikut: Pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir.

b. Elemen Algoritma Greedy

Elemen-elemen yang digunakan dalam penerapan algoritma greedy antara lain :

1. Himpunan Kandidat

Himpunan yang berisi elemen pembentuk solusi.

2. Himpunan Solusi

Himpunan yang terpilih sebagai solusi persoalan.

3. Fungsi Seleksi

Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal.

4. Fungsi Kelayakan

Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada.

5. Fungsi Solusi

Fungsi yang mengembalikan nilai boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap.

6. Fungsi Objektif

Fungsi yang mengoptimalkan solusi.

Pseudo-code algoritma greedy

Procedure greedy (input C : himpunan_kandidat, OutputS :himpunan_solusi)

{menentukan solusi optimum dari persoalan optimasi dengan algoritma

greedy

Masukan : himpunan kandidat C

Keluaran : himpunan solusi S }

Deklarasi x : kandidat ;

Algoritma :

S  {}

While (belum SOLUSI (S)) and (C ≠ {}) do

x  SELEKSI (C) ;

C  C – {x}

If LAYAK (S U {x} ) then S  S U {x}

Endif

Endwhile

{solusi (S) sudah diperoleh or C = {} }

Dalam menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy.

Pembuatan Prosedur Greedy dengan masukan berupa himpunan_kandidat dengan variable

C, dan keluaran berupa himpunan_solusi dengan variable S. Variabel x dideklarasikan

sebagai kandidat sementara yang dipilih.

Langkah algoritma greedy : inisialisasi awal himpunan_solusi dengan kosong. Selama

himpunan solusi belum ditemukan dan himpunan-kandidat tidak kosong, maka akan

dilakukan pemilihan sebuah kandidat dari himpunan_kandidat untuk mengisi variabel

sementara x, sehingga himpunan_kandidat menjadi berkurang satu dan himpunan kandidat

yang berkurang tadi menjadi himpunan kandidat yang baru. Jika anggota himpunan_solusi

merupakan anggota himpunan x, maka himpunan solusi yang baru adalah anggota dari

himpunan_solusi yang juga menjadi anggota dari himpunan x. Himpunan _solusi sudah diperoleh atau himpunan_kandidat =himpunan kosong.

B. Pemograman C++

Bahasa pemrograman yang memiliki sifat Pemrograman berorientasi objek, Untuk menyelesaikan masalah, C++ melakukan langkah pertama dengan menjelaskan class-class yang merupakan anak class yang dibuat sebelumnya sebagai abstraksi dari object-object fisik, Class tersebut berisi keadaan object, anggota-anggotanya dan kemampuan dari objectnya, Setelah beberapa Class dibuat kemudian masalah dipecahkan dengan Class.
Bahasa C adalah sebuah bahasa dasar tingkat tinggi yang sifatnya kompleks dan membangun logika atau algoritma.
Bahasa C adalah bahasa pemrograman prosedural yang memungkinkan kita untuk membuat prosedur dalam menyelesaikan suatu masalah.Bahasa tingkat tinggi merupakan bahasa yang mudah dipahami oleh manusia, C dan C++ merupakan contoh bahasa dari bahasa tingkat tinggi. Contoh lain dari bahasa tingkat tinggi adalah Pascal , Perl, Java, dan lain lain. Sedangkan bahasa tingkat rendah merupakan bahasa mesin atau bahasa asembly. Secara sederhana sebuah komputer hanya dapat mengeksekusi program yang ditulis dalam bahasa mesin. Oleh karena itu , jika suatu program ditulis dalam bahasa tingkat tinggi, maka program tersebut harus diproses dahulu sebelum bisa dijalankan dengan komputer.
Proses untuk untuk mengubah dari bahasa tinkaat tinggi ke bahasa tingkat rendah dalam bahasa pemrograman ada 2 tipe yaitu intrepenter dan compiler.
Bahasa pemrograman seperti C dan C++ merupakan contoh dari tipe compiler. Namun ada bahasa yang menggabungkan 2 tipe ini salah satunya adalah bahasa Java.

PERSOALAN UANG

Dengan menggunakan bahasa C, dilakukan pembuatan program sederhana dengan menggunakan algoritma Greedy yang dapat mengatasi persoalan uang.

#include <conio.h>

#include <stdio.h>

#define size 100

void sort(int[],int);

main() {

clrscr();

int x[size],i,n,uang,hasil[size];

printf("\nBanyaknya jenis koin atau uang: ");

scanf("%d",&n);

printf("\nMasukkan jenis koin atau uang (Rp): \n");

for(i=1;i<=n;i++) {

scanf("%d",&x[i]); }

sort(x,n);

printf("\nJenis koin atau uang yang tersedia (Rp): \n");

for(i=n;i>=1;i--) {

printf("%d \t",x[i]); }

printf("\n\nmasukkan nilai yang ingin dipecah: Rp ");

scanf("%d",&uang);

printf("\n\nHasil algoritma greedynya adalah: \n");

for(i=1;i<=n;i++) {

hasil[i]=uang/x[i];

uang=uang%x[i]; }

for(i=1;i<=n;i++) {

printf("\akoin Rp %d",x[i]);

printf("-an Sebanyak: %d keping",hasil[i]);

printf("\n"); }

printf("\n");

getch();

return 0; }

void sort(int a[],int siz) {

int pass,hold,j;

for(pass=1;pass<=siz-1;pass++) {

for(j=0;j<=siz-2;j++) {

if(a[j+1]) {

hold=a[j+1];

a[j+1]=a[j+2];

a[j+2]=hold;

}

}

}

}

Kode diatas merupakan source code dari program sederhana dalam bahasa C++ yang menggunakan

algoritma Greedy untuk menyelesaikan persoalan jenis koin.

Hasil Algoritma Greedy pada Penyelesaian Persoalan Koin Atau Uang dengan C++

Setelah program tersebut dijalankan maka akan meminta masukan banyaknya pecahan uang dan nilai masing-masing pecahan uang tersebut. Setelah itu program akan menampilkan urutan hasil dari

pecahan uang yang tersedia. Pada gambar, nampak masukan banyaknya koin adalah 2 dengan masukan jenis koin 6000, 3000 Kemudian program akan meminta masukan nilai uang yang ingin dipecah, pada gambar nampak nilai uang yang ingin dipecah adalah 3000. Setelah itu program akan menampilkan jumlah pecahan uang yang dibutuhkan untuk masing-masing pecahan. Untuk koin 6000-an sebanyak 0 keping dan koin 3000-an sebanyak 1 keping.

Logika Program

Apabila sudah mengetikkan listing programnya, disimpan koin.cpp

§  #include <stdio.h> merupakan Library untuk input/output pada program,tanpa menyertakan code ini kita tidak bisa melakukanpengoperasian input dan output.

§  #include<conio.h> merupakan fungsi library console i/o untuk memanggil fungsi input output untuk menggunakan perintah getch.

§  #define size  99 merupakan fungsi untuk menentukan batasan ukuran data yang ingin diinput. Apabila lebih dari 99 maka data yang sudah diinput tidak dapat di eksekusi.

§  void sort(int[],int); Merupakan Main procedure atau bisa dibilang sebagai program utama berbentuk prosedur untuk mengurutkan data yang akan kita masukan (input).

§  main() merupakan badan utama dari suatu progam.

sort(x,n), Merupakan fungsi untuk memanggil fungsi sort yang mengurutkan dari nilai terbesar sampai terkecil, dalam hal ini adalah variabel x dan n yanfg bertipe integer.

§  Merupakan fungsi perulangan for dimana nilai awal i adalah 1 sampai kondisi akhir nilai i kurang dari sama dengan n. Selama kondisi masih terpenuhi, maka akan dilakukan iterasi dengan menjalankan program hasil array sebagai hasil dari uang dibagi array x, dan uang sebagai hasil uang mod array x. Kemudian setelah iterasi berhasil, k merupakan hasil dari uang mod array x.

 §  Getch, Merupakan syntax untuk membaca hasil langsung dari console. Sedangkan return 0 merupakan pengembalian statement yang sudah diolah, dengan tanpa nilai.

§  void sort, Merupakan method dimana algoritma dimulai, disini dilakukan proses pengurutannya, sebelum menjadi output yang ditampilkan di layar fungsi ini harus di olah terlebih dahulu, setelah diolah kemudian ditampilkan dilayar.

KESIMPULAN

Algoritma greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu mendapatkan solusi terbaik (optimum), sehingga algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistem real-time dapat dilihat bagaimana algoritma greedy memiliki beberapa fungsionalitas dasar, yaitu:

1.      Fungsi untuk melakukan penelusuran masalah.

2.      Fungsi untuk memilih local maximum dari pilihan-pilihan yang ada tiap langkahnya.

3.      Fungsi untuk mengisikan nilai local maximum ke solusi keseluruhan.Fungsi yang menentukan apakah solusi telah didapatkan

DAFTAR PUSTAKA

https://sekarsri.wordpress.com/2014/04/17/pengertian-bahasa-pemrograman-c/

Simulasi_Pemilihan_koin_secara_greedy_dengan_game_ok.pdf

Read More