0/1 Sırt Çantası: Al veya Bırak
Ağırlık sınırı altında değeri en yükseğe çıkarın.
0/1 Sırt Çantası: Al veya Bırak, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 1. 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ırt Çantası Problemi
Ağırlık sınırı olan bir çantanız ve bir yığın öğeniz var. 0/1 sırt çantası problemi, çantayı aşırı doldurmadan hangi öğelerin değeri en üst düzeye çıkaracağını sorar. 🎒
Alın veya Bırakın
0/1 ifadesi, her öğenin ya tamamen alındığı ya da tamamen atlandığı anlamına gelir. Bir öğenin yarısını alamazsınız; her seçim evet veya hayırdır.
Açgözlü Yaklaşım Neden İşe Yaramaz
En ucuz veya en değerli öğeyi önce almak kapasiteyi boşa harcayabilir. Açgözlü kısayol burada işe yaramaz; gerçek kombinasyonları değerlendirmeniz gerekir.
İki Girdi
Size iki paralel liste verilir: her öğe için bir ağırlık ve bir değer, ayrıca bir kapasite. i öğesinin ağırlığı wt[i], değeri ise val[i] olur.
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Durumu Tanımlayın
dp[i][w], ilk i öğe kullanıldığında ve kapasite w olduğunda elde edilebilecek en iyi değer olsun. Durumu kesin biçimde adlandırmak işin asıl temelidir.
Atlama Seçeneği
i öğesini atlarsanız, değeriniz zaten sahip olduğunuz değer olur: dp[i-1][w]. Geri kalan öğeler için kapasite değişmeden kalır.
Alma Seçeneği
i öğesini alırsanız, değerini ekleyip kapasiteyi azaltırsınız: val[i] + dp[i-1][w - wt[i]]. Bu yalnızca w, wt[i]'den en az onun kadar büyükse geçerlidir.
Daha İyi Dalı Seçin
Yineleme bağıntısı, iki seçenekten büyük olanı maksimum ile tutar. Her hücre, kendisinden aşağıda daha önce hesaplanan yanıtlara güvenir.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])Temel Satır
Sıfır öğeyle, her kapasitede taşıyabileceğiniz değer sıfırdır. Bu temel durum, üzerine inşa etmek için ilk satırı tamamen sıfırlarla doldurur.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Tabloyu Doldurun
Dış döngüde öğeler, iç döngüde kapasiteler üzerinde ilerleyin. Her hücre yalnızca üst satırı okur; böylece tek bir tarama her şeyi doldurur.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Yanıtı Okuyun
Sağ alt hücre olan dp[n][cap], tüm öğeler ve tam kapasite için en yüksek değeri içerir. Bu tek hücre son yanıtınızdır.
Hızlı Kontrol
Temel 0/1 sırt çantası yineleme bağıntısını sınayın.
Özet
0/1 sırt çantası problemini öğrendiniz: her öğe alınır veya atlanır, dp[i][w] atlama ile alma seçeneklerinin en iyisini tutar ve dp[n][cap] yanıttır. 🎉
Sıkça Sorulan Sorular
“0/1 Sırt Çantası: Al veya Bırak” dersi ücretsiz mi?
Evet — “0/1 Sırt Çantası: Al veya Bırak” 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.
“0/1 Sırt Çantası: Al veya Bırak” dersinde ne öğreneceğim?
Ağırlık sınırı altında değeri en yükseğe çıkarı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 1. dersidir.
“0/1 Sırt Çantası: Al veya Bırak” 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