Pengertian Algoritma Greedy dan Contoh Program 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.

 contoh algoritma greedy pada C++ dengan contoh aplikasi penukaran koin logam

#include

#include

#define size 99

void sort(int[], int);

main()

{

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

printf("\n Banyak Koin :");

scanf("%d", &n);

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

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

{

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

}

sort(x,n);

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

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

{

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

printf("\n");

}

printf("\n");

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

scanf("%d", &uang);

printf("\n");

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

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

uang=uang%x[i];

}

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

{

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

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

printf("\n \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] < a[j+2])

{

hold=a[j+1];

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

a[j+2]=hold;

}

}

}

}

lengkap nya  download

Baca selengkapnya »