Greedy yaklaşım

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.

Örnek çözümü göster

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))

Kendini test et

Greedy her adımda neyi seçer?
- Yerel en iyiyi
- Rastgele birini
- Küresel en iyiyi
- İlk bulduğunu
Cevabı göster

Yerel en iyiyi — Yerel en iyiyi.
Greedy karar
```
amount ____ coin
```
Cevabı göster
```
amount -= coin
```
Greedy yaklaşım: kavramları eşleştir

greedy

Yerel en iyi
global

Tüm problem
backtrack

Yok
coin

Para

Sıradaki ders: Bozuk para

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler