Algoritma Greedy

Sedikit menggelitik pikiran saya, tulisan ini berkaitan dengan salah satu matakuliah yang sudah lama cukup berlalu, yaa Algoritma Greedy.

Algoritma Greedy merupakan salah satu algoritma yang paling populer dalam memecahkan kasus optimasi.

sesuai dengan namanya, Greedy berarti rakus atau ramak, prinsip dari algoritma ini adalah "take what you can get, now!" waaah dari prinsipnya saja kita sudah bisa membayangkan bagaimana cara kerja dari algoritma ini.

knapa bisa disebut tamak? mari saya beri contoh gampangnya.

misalnya, fulan mempunyai uang 1000 rupiah, ingin menukarkanya dalam bentuk receh,

tukaran receh yang tersedia adalah: 700,600,400,200,100.

Greedy selalu akan mengambil yang paling besar dulu sebagai langkah pertama, berarti dalam kasus ini akan diambil:

- 700 x 1 = 700

- 200 x 1 = 200

- 100 x 1 = 100

berarti uang 1000 dipecah menjadi 3 bagian (700,200,100) padahal akan lebih optimal bila hanya ditukar dengan 2 bagian (600,400) berarti memory yang akan terpakai pun akan lebih sedikit.

apakah sudah cukup jelas? bila sudah mari kita masuk kedalam contoh program (bahasa C):

‎#include<stdio.h>

Script ini berguna untuk menyatakan sesuatu pada kompiler agar membaca file bernama stdio.h saat pelaksanaan kompilasi

#include<conio.h>

Sript ini digunakan untuk menyatakan compiler agar dapat mengetahui compiler c pada library conio.h

#define size 99

Script ini berfungsi sebagai petunjuk bahwa prototypenya berada di file judul (header file) stdio.h. dan conio.h. 

void sort(int[],int);

main()

{

Script ini berguna untuk mendeklarasikan integer dan di kembalikan dalam keadaan void.

clrscr();

Script ini berfungsi untuk membersihkan atau menghapus layar output pada perintah / sintax sebelumnya.

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

printf("\n Banyak Koin :");

Disini kita mendeklarasikan integer x,i,n,uang dan hasil. Kemudian program akan mencetak kalimat yang berada dalam tanda kutip pada perintah printf, yaitu ”Banyak Koin :”

scanf("%d",&n);

Kalau script ini berfungsi agar program menganggap blank atau spasi dan tabulasi sebagai akhir dari suatu nilai data yang dimasukkan. Memasukan data tersebut menjadi suatu bentuk variabel berbentuk %d (membaca sebuah nilai integer desimal), kemudian menggunakan “&” agar menerima input berupa integer.

printf("\n \n Masukkan Jenis Koin: \n");

Script ini fungsinya sama dengan pada perintah printf sebelumnya, sehingga akan mengeluarkan output berupa kalimat “Masukkan Jenis Koin:”

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

{

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

}

sort(x,n);

Disini kita akan melakukan kondisi perulangan menggunakan perintah for serta tak lupa kita memasukkan parameternya. Lalu script scanf() fungsinya hamper sama pada perintah scanf sebelumnya, namun terdapat perbedaan saat kita mendeklarasikan parameternya sehingga program akan menerima input berupa integer. Sedangkan script sort merupakan perintah untuk mengurutkan, jadi angka yang diinput akan terbentuk secara berurutan.

printf("\n Koin yang Tersedia:");

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

{

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

printf("\n");

}

Disini proses algoritma greedy yang kita buat mulai dijalankan pada script ini. Sedangkan fungsi dari script-script tersebut sebelumnya telah dijelaskan di atas.

printf("\n");

printf("\n Masukkan Nilai yang Dipecah:");

scanf("%d",&uang);

printf("\n");

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

  

pada script di atas, proses algoritma greedy dijalankan, begitu pula dengan proses perulangan. Proses perulangan ini dilakukan sampai program menemukan solusi optimum yang dicar.

{

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

uang=uang%x[i];

}

Kemudian proses kalkulasi / perhitungan dilakukan disini.

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

{

printf("Keping %d",x[i]);

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

printf("\n\n");

}

Dan akhirnya hasil dari proses kalkulasi / perhitungan untuk mencari solusi optimum yang dibutuhkan akan dicetak menggunakan perintah di atas.

getch();

return 0;

}

Perintah ini berarti  Jika nilai karakter yang diinginkan dimasukkan tanpa diakhiri dengan penekanan tombol Enter dan karakter yang diketikkan tidak tampak di layar monitor.

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] < a[j+2])

{

hold=a[j+1];

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

a[j+2]=hold;

}

}

}

}

Script di atas berguna untuk mengembalikan kondisi program seperti permulaan kembali (kembali ke awal).

NB : Script berupa tanda kurung kurawal (buka / tutup “{}”) fungsinya hampir sama pada bahasa pemrograma java, yaitu menandakan suatu sctipt yang berada di dalamnya merupakan suatu blok program

Berikut hasil dari script program yang telah dibuat :

Best Regard,

Syalay-Chan