Alanı İyileştirilmiş Sırt Çantası
2B yapıyı tek satıra indirin.
Alanı İyileştirilmiş Sırt Çantası, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Belleği Neden Optimize Etmeli
Tam bir tablo n çarpı cap kadar bellek kullanır; büyük girdilerde bu miktar aşırı büyüyebilir. Bellek optimizasyonu bunu yeniden kullandığınız tek bir satıra indirger.
Yalnızca Son Satır Önemlidir
Her hücrenin yalnızca önceki satırı okuduğuna, daha eski hiçbir şeyi okumadığına dikkat edin. Bu nedenle tüm tabloyu aynı anda saklamanız gerekmez.
Tek Diziye İndirgeyin
Uzunluğu cap+1 olan tek bir dp dizisi tutun. Her öğeyi işlerken yeni satırı temsil etmesi için bu dizinin üzerine yerinde yazın.
dp = [0] * (cap + 1)Yeniden Kullanma Tuzağı
Kapasiteyi soldan sağa tararsanız dp[w - wt[i]] aynı öğe için zaten güncellenmiş olabilir. Bu, i öğesini iki kez almanıza izin verir.
Kapasiteyi Geriye Doğru İlerletin
Çözüm, kapasiteyi büyükten küçüğe doğru döngüye almaktır. Geriye doğru ilerlemek, dp[w - wt[i]] değerinin hâlâ önceki öğenin değerini tutmasını garanti eder.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Geriye Doğru İlerlemek Neden İşe Yarar
dp[w] değerini hesaplarken daha küçük indeks olan w - wt[i] bu turda hâlâ değiştirilmemiştir; bu nedenle amaçlandığı gibi üst satırı yansıtır.
Ağırlıkta Erken Durdurun
wt[i]'nin altındaki kapasiteler öğeyi sığdıramaz; bu nedenle döngü wt[i] değerinde durur. Bunları atlamak birkaç zararsız döngü adımını kaydeder.
Tam Döngü
Çözümün tamamı tek bir dizi üzerindeki iki iç içe döngüdür. Dışarıda öğeler, içeride kapasite geriye doğru ilerler ve yanıt kendiliğinden elde edilir.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Son Hücreyi Okuyun
Tüm öğeler işlendikten sonra dp[cap] en yüksek değeri içerir. Çok daha az bellek kullanmasına rağmen, 2B tablonun vereceği sayının aynısını verir.
Aynı Süre, Daha Az Bellek
Algoritmayı hızlandırmadınız; çalışma hâlâ n çarpı cap mertebesindedir. Yalnızca belleği karesel düzeyden doğrusal düzeye indirdiniz.
Ne Zaman İşe Yarar
Bu yöntem, cap büyük olduğunda ve 2B tablonun bellek sınırını aşacağı durumlarda sizi kurtarır. Ezberlemeye değer, yarışmalarda sık kullanılan bir tekniktir.
Hızlı Kontrol
1B sırt çantası için temel kuralı sınayın.
Özet
2B tabloyu tek bir diziye indirdiniz ve doğru kalmak için kapasiteyi geriye doğru döngüye aldınız; böylece karesel bellek kullanımını doğrusalla değiştirdiniz. 🚀
Sıkça Sorulan Sorular
“Alanı İyileştirilmiş Sırt Çantası” dersi ücretsiz mi?
Evet — “Alanı İyileştirilmiş Sırt Çantası” 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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Alanı İyileştirilmiş Sırt Çantası” dersinde ne öğreneceğim?
2B yapıyı tek satıra indirin. Coding Interview Prep 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.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, 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 2. dersidir.
“Alanı İyileştirilmiş Sırt Çantası” 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep 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