İçeriğe geç

Greedy ne zaman işe yarar

Ders 1 / 5 · 5 dk

Greedy ne zaman işe yarar

Adım 1/9

Greedy (açgözlü) yaklaşımın tek kuralı var: hâlâ sığan en büyük parayı al ve asla geri dönme.

Fikir

Greedy (açgözlü) algoritma, o an en iyi görünen hamleyi yapar ve ona bir daha dönmez. Arama ağacı yok, geri alma yok: tek geçiş.

Bu ancak yerel bir kazanç sana daha iyi bir genel cevabı asla kaybettirmiyorsa doğrudur. Genelde kullanılan ispat bir exchange argument'tır: herhangi bir optimal cevabı al, içindeki bir seçimi greedy seçimle yer değiştir (swap) ve sonucun hâlâ optimal olduğunu göster. Bu yer değiştirme her seferinde ayakta kalıyorsa greedy güvenlidir. Güvenli olmadığını göstermek için tek bir karşı örnek yeter.

Gerçek hayattan örnek

Kasada para üstü verdiğini düşün. 25, 10, 5 ve 1'lik paralarla, hâlâ sığan en büyük parayı almak her zaman optimaldir. 1, 3 ve 4'lük bir para birimi bas; aynı refleks altı için 4 + 1 + 1 öder, oysa iki tane 3 yeterdi.

Kod

Sıra sende

Bu kod ne yazdırır?

print(greedy_coins([1, 5, 7], 10))

Mini quiz

1 / 3

Greedy bir algoritma asla ne yapmaz?