Alt Küme Toplamı ve Bölümleme
Seçilen bir alt kümeyle hedefe ulaşın.
Alt Küme Toplamı ve Bölümleme, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 4. 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.
Alt Küme Toplamı Sorusu
Sayılar ve bir hedef verildiğinde, herhangi bir alt kümenin toplamı tam olarak bu hedefe eşit olabilir mi? Bu, değerin ağırlığa eşit olduğu bir sırt çantası problemidir.
Değer Değil, Mantıksal DP
Burada maksimum değeri değil, ulaşılabilirliği izlersiniz. dp[s], herhangi bir alt kümenin toplamı tam olarak s olduğunda doğru olsun.
dp = [False] * (target + 1)
dp[0] = TrueSıfıra Her Zaman Ulaşılabilir
Boş alt kümenin toplamı sıfırdır; bu nedenle dp[0] başlangıçta doğrudur. Diğer tüm toplamlar, bir sayı ulaşılabilir olduklarını kanıtlayana kadar yanlış başlar.
Geçiş
Her sayı için, s - num zaten ulaşılabiliyorsa s değerini de ulaşılabilir olarak işaretleyin. Tek bir sayı, birçok toplamı doğru duruma getirebilir.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]Yine Geriye Doğru
Her sayı en fazla bir kez kullanıldığından, iç döngü tıpkı 0/1 sırt çantasında olduğu gibi geriye doğru ilerler. İleri doğru ilerlemek bir sayıyı yeniden kullanır.
Sonucu Okuyun
Tüm sayılar işlendiğinde sorunun yanıtını dp[target] verir. Doğru değer, geçerli bir alt kümenin var olduğunu; yanlış değer ise bunun imkânsız olduğunu gösterir.
Bölme Problemine Geçin
Bölme problemi, diziyi toplamları eşit iki parçaya ayırıp ayıramayacağınızı sorar. Bu problem doğrudan alt küme toplamına indirgenir.
Toplamı İkiye Bölün
Toplam tekse eşit parçalar oluşturmak imkânsızdır; bu nedenle hemen hayır yanıtını verin. Aksi durumda hedef basitçe total // 2 olur.
total = sum(nums)
if total % 2:
return False
target = total // 2Alt Küme Toplamını Yeniden Kullanın
Şimdi yalnızca bir alt kümenin total // 2 değerine ulaşıp ulaşmadığını sorun. Bir yarı hedefe ulaşıyorsa kalanlar otomatik olarak eşleşen ikinci yarıyı oluşturur.
Karmaşıklık
Maliyet n çarpı hedef mertebesindedir; bu, sözde polinom bir sınırdır. Hedef küçük olduğunda hızlı, toplamlar çok büyük olduğunda yavaştır.
Tek Bir Problem Ailesi
Alt küme toplamı, bölümleme ve 0/1 sırt çantası aynı motoru paylaşır. Al ya da bırak yapısını fark ettiğinizde aynı döngüyü yeniden kullanabilirsiniz.
Hızlı Kontrol
Bölümleme indirgemesini test edin.
Tekrar
Alt küme toplamını boolean DP ve geriye doğru bir döngüyle çözdünüz, ardından bölümlemeyi toplam // 2 değerine ulaşmaya indirgediniz. Aynı motor, yeni kazanımlar. ✅
Sıkça Sorulan Sorular
“Alt Küme Toplamı ve Bölümleme” dersi ücretsiz mi?
Evet — “Alt Küme Toplamı ve Bölümleme” 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.
“Alt Küme Toplamı ve Bölümleme” dersinde ne öğreneceğim?
Seçilen bir alt kümeyle hedefe ulaşı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 4. dersidir.
“Alt Küme Toplamı ve Bölümleme” 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