Sınırsız ve Para Üstü DP'si
Öğeleri istediğiniz sayıda kullanın.
Sınırsız ve Para Üstü DP'si, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
Sınırsız Öğeler
Sınırsız sırt çantası probleminde her öğe istediğiniz kadar alınabilir. Sabit bir yığın yerine, otomatlardaki madeni paraları düşünün.
Tek Küçük Değişiklik
0/1 problemine göre yalnızca döngünün yönü değişir. Sınırsız öğelerde kapasiteyi ileri doğru, küçükten büyüğe tararsınız.
İleri Doğru Yeniden Kullanım Esastır
İleri doğru giderken dp[w - coin] aynı öğeyi zaten içerebilir. Bu kasıtlı yeniden kullanım, öğeyi tekrar alabilmenizi sağlar.
Madeni Para Bozdurma Problemiyle Tanışın
Klasik madeni para bozdurma problemi, bir miktarı oluşturmak için gereken en az madeni para sayısını sorar. Bu, maksimum yerine minimum kullanan sınırsız DP'dir.
Durumu Tanımlayın
dp[a], a miktarını oluşturmak için gereken en az madeni para sayısı olsun. Sıfır miktarı için hiç madeni para gerekmediğinden dp[0] = 0 ile başlayın.
dp = [float("inf")] * (amount + 1)
dp[0] = 0İmkânsız Durumlar İçin Sonsuzluk Kullanın
Ulaşılamayan miktarlar başlangıçta sonsuzluk değerini alır. Bir miktar sonunda sonsuz kalırsa hiçbir madeni para kombinasyonu onu oluşturamaz.
Geçiş
Her madeni para için ulaşabileceği her miktarı iyileştirmeyi deneyin. Geride kalan daha küçük miktar için bulunan değere bir madeni para ekleyin.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)İleri Sıra Neden Önemlidir
Miktarları yukarı doğru taramak, dp[a - coin] değerinin bu madeni parayı zaten sayabilmesini sağlar. Tek bir madeni paranın birden çok kez katkıda bulunması böyle mümkün olur.
Bunun Yerine Yolları Sayın
Her miktarı oluşturmanın kaç yolu olduğunu saymak için minimum artı 1 yerine toplam kullanın. Madeni para döngüsünü dışarıda tutmak, sıralamaları iki kez saymanızı önler.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Sonucu Okuyun
Yanıtınız dp[amount] içindedir. Minimum sürümünde sonsuz değer, hedefin oluşturulmasının imkânsız olduğu anlamına gelir.
0/1 ve Sınırsız Sürüm
Tek değişikliği hatırlayın: kapasiteyi geriye doğru ilerletmek her öğenin bir kez kullanılmasını, ileri doğru ilerletmek ise sınırsız kullanımı sağlar. Tablo aynı, tarama yönü terstir.
Hızlı Kontrol
Sırt çantasını sınırsız yapan özelliği sınayın.
Özet
Sınırsız yeniden kullanım için döngüyü ileri çevirdiniz ve en az madeni para sayısı için minimum, toplam yol sayısı için toplam kullanan para bozdurma problemini kurdunuz. 💰
Sıkça Sorulan Sorular
“Sınırsız ve Para Üstü DP'si” dersi ücretsiz mi?
Evet — “Sınırsız ve Para Üstü DP'si” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“Sınırsız ve Para Üstü DP'si” dersinde ne öğreneceğim?
Öğeleri istediğiniz sayıda kullanın. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Sınırsız ve Para Üstü DP'si” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- 0/1 Sırt Çantası: Al veya Bırak
- Alanı İyileştirilmiş Sırt Çantası
- Sınırsız ve Para Üstü DP'si
- Alt Küme Toplamı ve Bölümleme