Greedy sınırları

Greedy'nin her zaman en iyiyi vermediğini öğrenirsin.

Greedy sınırları

Greedy her zaman en iyiyi vermez. Örnek: [1, 3, 4] ile tutar 6. Greedy [4, 1, 1] (3 para) verir; en iyi [3, 3] (2 para).

Böyle durumlarda dinamik programlama daha iyidir; greedy yanlış seçim yapar.

Bu yüzden greedy'yi uygulamadan önce problemin yapısını doğrulamak gerekir; aksi halde yanlış sonuç alınır.

Karşı örnek

Bir algoritmanın hatalı olduğunu gösteren giriş örneğine karşı örnek denir. Greedy sınırlarını test etmek için kullanılır.

Yukarıdaki [1, 3, 4] ve 6 örneği buna bir örnektir; greedy 3 para verir, optimim 2.

Karşı örnekler, algoritma seçiminde belirleyicidir; yanlış yaklaşımı erken ele verir.

Uygulama Greedy'nin kötü tarafı

greedy_bad(coins, amount) yaz. Greedy çözümün para sayısını döndür. print(greedy_bad([1, 3, 4], 6)) ile 3 yazdır.

Örnek çözümü göster

def greedy_bad(coins, amount):
    # Greedy kötü örnek
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount = amount % coin
    return count
print(greedy_bad([1, 3, 4], 6))

Kendini test et

Greedy sınırları: kavramları eşleştir

counter-example

Hatalı gösterir
greedy

Yerel en iyi
DP

Küresel en iyi
optimim

En iyi
[1, 3, 4] ve 6 için greedy kaç para verir?
- 1
- 2
- 4
- 3
Cevabı göster

3 — 3 (4 + 1 + 1).

Optimim çözüm

En az para ile 6: ____ sonucu

Cevabı göster

En az para ile 6: 3, 3 sonucu

Sıradaki ders: Özet - Greedy

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler