Javada Para Üstü Verme Programı-Açgözlü Yaklaşım(Greedy Approach)

Merhaba arkadaşlar bugün yapay zekada kullanılan bir yöntem olan açgözlü yaklaşımı basitçe javada yapacağız.Öncelikle Açgözlü Yaklaşım(Greedy Approach) nedir ondan bahsedelim.Açgözlü yaklaşım bir proplemi çözerken ” sonuca en yakın ”  seçimi yapan yaklaşımdır.Algoritmanın tek düşündüğü sonuca bir an önce ulaşmak olduğundan her zaman en iyi çözümü veremeyebilir.Fakat para üstü proplemlerinde kusursuz çalışır.Şimdi bu algoritmanın dezavantajını ve  avantajını iki örnek üzerinde görelim.

Öncelikle şöyle bir şey düşünelim.Elimizde bir 5  birimlik çuval var ve biz buna çeşitli boyutlara ve değerlere sahip eşyaları doldurarak en değerli çuvalı elde etmeye çalışacağız.Elimizdeki eşyaların değerleri şöyle olsun:

1. A eşyası =4 Birim = 10 değerinde
2. B eşyası = 3 Birim = 8 değerinde
3. C eşyası = 2.5 Birim = 6 değerinde

Şimdi açgözlü yaklaşımı kullanırsak burda hedefimiz çuvalı direkt en değerlileri ile doldurmak  olur..Bu yüzden en fazla değere sahip A yı seçip çuvala atarız.Çuvalımız 10 değerinde olacaktır.Burda 5 birim hacminde çuvalımızı  4 birimle doldurduk ve 10 değerinde bir çuval elde ettik.Fakat 1 birimimiz hala boş ve burayı dolduramıyoruz.Aç gözlü yaklaşımı kullanmayıp B ile doldursaydık, çuvalımız 3 birim dolu,2 birim boş ve 8 değerinde olacaktı.Fakat burda en iyi çözüm 2 tane C yi çuvalımıza atarak 5 birimin hepsini kullanmak ve toplam 12 değerini elde etmek olacaktı.İşte açgözlü yaklaşımın en büyük dezavantajlarından biri budur..

Şimdi de avantajlı olduğu durum olan para sayma proplemine geçelim.Kendimizi bir tezgahta çalışan olarak düşünelim ve amacımız  para üstlerini en az parayla vermek olsun ve bunun için elimizde her paradan  yeterli sayıda mevcut olsun..Müşterimiz gelip alışveriş yaptığında 3.65 tl lik bir para üstü vermemiz gereksin.Elimizde de şu para birimleri var diye kabul edelim:

5 Kuruş ==> 10 Kuruş ==> 25 Kuruş ==> 50 Kuruş ==> 1 Tl ==> 5 Tl

Şimdi açgözlü yaklaşımda amaç para üstünü bir an önce vermek olduğundan direkt en yüksek parayla bu işi halletmeye çalışacaktır.Elimizde en fazla 5 Tl var fakat bu, para üstünden fazla olduğundan bunu kullanamayız.O yüzden sonraki en büyük para birimi olan 1 Tl ile vermeye çalışıyoruz. 1 Tane 1 Tl versek  2.65 TL kalıyor..1 tane daha versek 1.65,1 tane daha versek 0.65 tl kalıyor.Artık 1 tl den daha düşük para üstü kaldığından 1 tl veremiyoruz.Bir sonraki en büyük para birimi olan 50 kuruş a geçiyoruz ve 1 tane 50 kuruş verince 0.15 tl kalıyor.Aynı mantıkla yine 50 kuruş veremediğimizden ,diğer para birimi olan 25 kuruşa geçiyoruz.25 kuruş da para üstünden büyük olduğundan bir sonraki para birimi olan 10 kuruşa geçiyoruz ve 5 kuruş kalıyor.Onu da bir sonraki para birimi olan 5 kuruşla ödüyoruz ve proplemi çözüyoruz.Toplam ödediğimiz paralar:

3 Tane  1 Tl ==> 1 Tane 50 Kuruş ==> 1 Tane 10 Kuruş ==> 1 tane 5 Kuruş  ==> Toplam 6 Para ile bu işlemi gerçekleştirmiş oluyoruz ve bu da zaten en iyi çözümümüz oluyor.

Gördüğünüz gibi burda açgözlü yaklaşım proplemimizi gayet iyi şekilde çözmekte..Para üstü proplemlerine benzer proplemlerde algoritmamız gayet avantajlı..

Bu da javada yaptığım basit bir örneği..Kuruş olarak para üstünü alıp,hangi para biriminden kaç tane verileceğini hesaplıyor..

[java]

public class Greedy_ParaUstu {

//Para birimlerimizi kurus cinsinden tanimliyoruz
static int[] arrParaBirimleri = {1, 5, 10, 25, 50, 100, 500};

//Daha guzel gozuksun diye para birimleriyle ayni indexte Turkce karsiliklarini yaziyoruz
static String[] arrParaTurkceKarsilik = {" 1 Kuruş", "5 Kuruş", "10 Kuruş", "25 Kuruş", "50 Kuruş", "1 TL", "5 Tl"};

public static void main(String[] args) {
paraUstu(365);//Kurus cinsinden parayi aliyoruz
}

public static void paraUstu(int paraUstu) {
//En buyuk para biriminden ,en kucuk para birimine kadar dolas
for (int i = arrParaBirimleri.length - 1; i >= 0; i--) {
//i. Paradan kac tane verildigini saymak icin sayac tuttuk
int sayac = 0;
//Verecegimiz para,para ustunden buyuk oldugu surece calis
while (paraUstu >= arrParaBirimleri[i]) {
//her para ustu verdiginde sayaci bir artir
sayac++;
//Verilen parayi,para ustunden cikar
paraUstu = paraUstu - arrParaBirimleri[i];
}
//eger para birimi kullanilmissa,kac tane kullanildigini ekrana yaz
if (sayac > 0) {
System.out.println(sayac + " Tane " + arrParaTurkceKarsilik[i]);
}
}
}
}

[/java]

Çıktı:

3 Tane 1 TL

1 Tane 50 Kuruş

1 Tane 10 Kuruş

1 Tane 5 Kuruş