30
Açgözlü algoritma yaklaşımı ile bozuk para seçimi problemi nasıl çözülür?

Açgözlü algoritmaya kullanılarak en az sayıda bozuk para seçme probleminin çözümü.

Açgözlü algoritma
Açgözlü algoritma, özellikle optimizasyon problemlerinin her bir adımında o adıma en uygun seçim yapılması ve bu tercihin problemin tamamının çözümü için kullanılmasıdır.

Örnek
Bir para biriminin 1, 7 ve 10 liralık bozuk parası bulunmaktadır. En az bozuk para adedi kullanarak verilen bir miktar parayı elde etmek için nasıl bir algoritma izlenmelidir.

Çözüm
Açgözlü algoritma ile yapılacak bir çözümde bu probleme şöyle yaklaşılır:
 
Her adımda olası en büyük bozuk parayı seç. Öyle ki toplam, verilen miktarı (hedef değeri) geçmesin.

Hedef değer 19 lirayı elde etmek olduğunda:
  • 10 lira ile başla. Sonuç (10) hedefi aşmadığı için devam et.
  • 10 lira daha ekle. Sonuç (10+10=20) hedefi aştığı için ikinci büyük para (7 lira) ile devam et.
  • 7 lira ekle. Sonuç (10+7=17) hedefi aşmadığı için devam et.
  • 7 lira daha ekle. Sonuç (17+7=24) hedefi aştığı için sıradaki en büyük para (1 lira) ile devam et.
  • 1 lira ekle. Sonuç (17+1=18) hedefi aşmadığı için devam et.
  • 1 lira ekle. Sonuç (18+1=19) hedef ile aynı olduğu için dur.
Sonuç olarak 10+7+1+1 olmak üzere 4 adet bozuk para kullanılmalıdır.

Hatalı çözüm
15 lira elde etmek üzere bu algoritma çalıştırıldığında çözüm, 10+1+1+1+1+1 olmak üzere 6 adet bozuk para olarak bulunur. Faka bu problemin optimum (en iyi) çözümü 7+7+1 olmak üzere 3 adet bozuk paradır.

Sonuç
Örneklerde de görüldüğü gibi açgözlü yaklaşım kaba kuvvet, geri izleme, dal sınır algoritmalarında olduğu gibi her optimizasyon problemi için her zaman en iyi çözümü bulmayı garanti etmez.
Bu alana not ekleyebilirsiniz.
Başka bir sorunuz mu var?
Yorumlar (1)
Katılıyor musun?
00

Peki 4 adet 5 var ayrı ayrı 4 adet de 10.

15.25.45 bunun nasıl çözerim?


15.12.2023

Bu Yoruma Cevap Yaz

İlgili Kayıtlar
İlginizi Çekebilir