Pengertian Algoritma Greedy dan Contoh Program Menggunakan Algoritma Greedy

Assalamu'alaikum warahmatullahi wabarakatuh

Hey kawan blogger, sudah dibilang kan saya itu kalo udah sekali nulis maunya nulis terus. hehe :p

Kali ini saya mau berbagi tentang program C++ yang menggunakan Algoritma Greedy.

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi. Prinsip greedy: “take what you can get now!”. Algoritma greedy membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Pada setiap langkah, kita membuat pilihan optimum lokal (local optimum) dengan harapan bahwa langkah sisanya  mengarah ke solusi optimum global (global optimum). 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.

Nah di bawah ini merupakan contoh coding programnya:

#include <conio.h>

#include <stdio.h>

#define size 99

void sort(int[],int);

main() {

clrscr();

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

printf("\nbanyaknya jenis koin: ");

scanf("%d",&n);

printf("\nmasukkan jenis koin (Rp): \n");

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

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

sort(x,n);

printf("\njenis koin 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;

}

}

}

}


Output dari program di atas adalah sebagai berikut:

Logika dari coding program di atas adalah sebagai berikut:

#include <conio.h>

peryataan conio.h. adalah library pada C yang digunakan untuk mengkoneksikan pernyataan clrscr() dengan program yang kita buat. Tanpa menggunakan library ini, kita tidak bisa menggunakan fungsi prototype seperti: gotoxy(), clrscr(), clreol().

#include <stdio.h>

Dalam c++ jika kita menginginkan penggunaan input dan output, atau bisa diartikan sebagai standard library yang berfungsi untuk I/O  package maksudnya digunakan jika kita ingin pada program kita menggunakan fungsi standard input atau output bisa dikatakan seperti portable input/output package. Tanpa menggunakan library ini, kita tidak bisa menggunakan perintah-perintah input/output pada program kita.

#define size 99

Library di atas berguna untuk menentukan size dari inputan banyak datanya adalah 99, artinya jika data lebih banyak dari 99, maka program akan berhenti mengeksekusi.

void sort(int[],int);

Pernyataan diatas adalah main procedure (prosedur utama dalam program ini). Pada program ini, program utama berbentuk prosedur untuk mengurutkan data yang kita input, disini yang akan diurutkan adalah variable masukan dari int[] dan int.

main() {

Pernyataan di atas digunakan sebagai badan program. Fungsinya sama seperti public.static.void.main(String args[]) { pada bahasa pemrograman java.

clrscr();

Pernyataan di atas digunakan untuk membersihkan layar ketika program dieksekusi.

int x[size],i,n,uang,hasil[size];
Pernyataan di atas digunakan untuk mendefinisikan variable yang akan digunakan dalam programnya. Tanda kurung siku [ ] menandakan variable tersebut bertipe array.

printf("\nbanyaknya jenis koin: ");

Pernyataan printf di atas digunakan untuk mencetak tulisan yang ada diantara tanda kutip “ ”. \n digunakan untuk member jeda (enter) pada saat program dieksekusi.

scanf("%d",&n);

Pernyataan scanf digunakan untuk menyimpan angka yang kita input ketika program dieksekusi. Disini terdapat %d yang mengartikan data inputan akan ditampilkan dalam bentuk decimal, dan &n mengartikan data inputan akan disimpan sementara pada variable n.

for(i=1;i<=n;i++) {
hasil[i]=uang/x[i];
uang=uang%x[i]; }

Pernyataan for di atas digunakan sebagai kondisi perulangan pada program, sedangkan pernyataan hasil[i]=uang/x[i]; digunakan sebegai rumus perhitungan untuk mendapatkan kombinasi koin apa saja yang digunakan untuk menukarkan koin yang ingin kita tukarkan dengan koin yang tersedia, lalu pernyataan uang=uang%x[i]; digunakan untuk menentukan berapa banyaknya kombinasi koin dalam pertukaran koinnya.

getch();

berguna unutk membaca sebuah karakter, bisa juga membaca tombol, getch() tidak akan menampilkan karakter dari tombol yang ditekan. Sebuah getch() bisa pula digunakan untuk menunggu sembarang tombol ditekan. Pada keadaan seperti ini, hasil dari fungsi ini tidak perlu diletakkan ke variable, atau dipascal dapat diartikan sebagai readln

return 0; }

angka 0 ini akan dikembalikan kepada sistem operasi. Nilai ini digunakan oleh sistem operasi untuk disimpan di variabel ERRORLEVEL pada MS DOS, dimana 0 artinya ‘sukses’.

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; } } } }

Blok pernyataan di atas digunakan untuk mengurutkan angka yang telah kita input pada saat program dieksekusi.

Sekian yang dapat saya bagian mengenai Algoritma Greedy dan contoh programnya. Semoga bermanfaat bagi yang membacanya. Akhir kata, terima kasih dan ...

Wassalamu'alaikum warahmatullahi wabarakatuh