Greedy sınırları
- Algoritmalar kursu
- Orta seviye
- Ders 63/80
- 4 dk
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.
Başlangıç kodu
def greedy_bad(coins, amount):
# Greedy kötü örnekÖrnek çözüm
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))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Greedy sınırları: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
counter-example |
Hatalı gösterir |
greedy |
Yerel en iyi |
DP |
Küresel en iyi |
optimim |
En iyi |
2 [1, 3, 4] ve 6 için greedy kaç para verir?
- 1
- 2
- 4
- 3 Doğru cevap
Açıklama: 3 (4 + 1 + 1).
3 Optimim çözüm
En az para ile 6: ____ sonucuEn az para ile 6: 3, 3 sonucuAçıklama: 3, 3 doğru.