Algoritma Greedy

Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah, pada setiap langkah:

• mengambil pilihan yang terbaik yang dapat diperoleh saat itu.
• berharap bahwa dengan memilih optimum lokal, pada setiap langkah akan mencapai optimum global.

Algoritma greedy mengasumsikan bahwa optimum lokal merupakan bagian dari optimum global.

Prinsip algoritma greedy adalah: “take what you can get now!”. Ambil apa yang anda peroleh sekarang! Prinsip ini juga dipakai dalam pemecahan masalah optimasi. Dalam kehidupan sehari-hari, kita juga pernah menggunakan prinsip greedy, misalnya:

• Memilih jurusan di Perguruan Tinggi
• Memilih jalur tersingkat dari Bandung ke Jakarta.
• Penukaran uang.

Contoh :

Uang sejumlah 5000 ingin ditukar dengan pecahan 500,1000,2000. Maka ada beberapa pilihan cara penukaran yaitu :

• 5000 = 500 + 500 + 500 + 500 + 500 + 500 + 500 + 500 (8 lembar)
• 5000= 500 + 500 + 1000 + 1000 + 1000 (5 lembar)
• 5000 = 1000 + 1000 + 1000 + 1000 + 1000 (5 lembar)

…..

…..

• 5000 = 1000 + 2000 + 2000 (3 lembar)

Maka solusi optimum untuk contoh di atas adalah jumlah minimum yaitu 3 lembar. Berikut ini adalah listing program yang dibuat dengan bahasa C untuk menyelesaikan masalah tersebut :

A. Listing Program

#include
#include
int jml,a,b,c,d,e,f,koin;
void main()
{
clrscr();
koin=0;
printf(”Input jumlah uang : “);
scanf (”%d”,&jml);
printf (”Input nilai koin A : “);
scanf (”%d”,&a);
printf (”Input nilai koin B : “);
scanf (”%d”,&b);
printf (”Input nilai koin C : “);
scanf (”%d”,&c);
if (a>b & b>c)
{
d=a;
e=b;
f=c;
}
else if (a>c & c>b)
{
d=a;
e=c;
f=b;
}
else if (b>a & a>c)
{
d=b;
e=a;
f=c;
}
else if (b>c & c>a)
{
d=b;
e=c;
f=a;
}
else if (c>a & a>b)
{
d=c;
e=a;
f=b;
}
else if (c>b & b>a)
{
d=c;
e=b;
f=a;
}
while (jml>=d)
{
jml= jml-d;
koin = koin++;
}
while (jml>=e)
{
jml=jml-e;
koin = koin++;
}
while (jml>=f)
{
jml=jml-f;
koin = koin++;
}
printf (”Banyaknya koin adalah %d koin”,koin);
getch();
}

B. Output Program

Posted in: Programming