Greedy yaklaşım
- Algoritmalar kursu
- Orta seviye
- Ders 61/80
- 4 dk
Her adımda yerel en iyiyi seçen yaklaşımı öğrenirsin.
Greedy yaklaşım
Greedy algoritmalar her adımda yerel en iyiyi seçer ve geri dönmez. Basit ve hızlıdır.
Her zaman küresel en iyi sonucu vermeyebilir; bu yüzden doğru problem seçmek önemlidir.
Greedy, Huffman kodlama, Kruskal ve Dijkstra gibi algoritmaların temelini oluşturur; verimli çalışır.
Yerel ve küresel
Greedy bir karar geri alınamaz. Bu yüzden yerel seçimler küresel en iyiyi oluşturuyorsa greedy çalışır.
Aksi halde farklı bir strateji (DP, dal-sınır) gerekir; greedy yetersiz kalır.
Bu yüzden greedy'yi uygulmadan önce problemin greedy-choice property'sine sahip olduğunu doğrulamak gerekir.
Uygulama En büyük parayı al
greedy_one(coins, amount) yaz. En büyük parayı alabildiğin kadar alan bir adımlık greedy yaz. Döndürdüğü değer: en büyük paranın kullanım sayısı. print(greedy_one([25, 10, 5, 1], 63)) ile 2 yazdır.
Başlangıç kodu
def greedy_one(coins, amount):
# En büyük parayı sayÖrnek çözüm
def greedy_one(coins, amount):
# En büyük parayı say
coins.sort(reverse=True)
largest = coins[0]
return amount // largest
print(greedy_one([25, 10, 5, 1], 63))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Greedy her adımda neyi seçer?
- Yerel en iyiyi Doğru cevap
- Rastgele birini
- Küresel en iyiyi
- İlk bulduğunu
Açıklama: Yerel en iyiyi.
2 Greedy karar
amount ____ coinamount -= coinAçıklama: -= doğru.
3 Greedy yaklaşım: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
greedy |
Yerel en iyi |
global |
Tüm problem |
backtrack |
Yok |
coin |
Para |