Sınırsız Sırt Çantası ve Bozuk Para Değişimi II
Kapasiteyi ileri yönde yineleyerek öğelerin tekrar kullanılmasına izin verin; bu çeşitlemeyle bozuk para değişimi II’yi (yol sayısını sayma) ve çubuk kesme problemlerini çözün.
Sınırsız Sırt Çantası ve Bozuk Para Değişimi II, CoddyKit'te ücretsiz bir DSA 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, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Sınırsız Sırt Çantası Kavramı
Sınırsız Sırt Çantası probleminde her öğe istenilen sayıda alınabilir (her öğenin en fazla bir kez kullanıldığı 0/1 sırt çantasının aksine). Durum tanımı aynıdır: dp[c] = c kapasitesiyle elde edilebilecek en yüksek değer; ancak gezinme yönü değişir. Öğeler yeniden kullanılabildiği için dp[c] değerini güncellerken mevcut öğenin tekrar kullanılmasına izin vermek isteriz; bu nedenle kapasiteyi soldan sağa (ileri yönde) gezeriz.
İleri Yönde Gezinme Yeniden Kullanımı Sağlar
0/1 sırt çantasında yeniden kullanımı önlemek için sağdan sola gezdiğimizi hatırlayın. Sınırsız sırt çantasında bunun tersini yaparız: soldan sağa gezeriz. dp[c] hesaplanırken dp[c-w] mevcut geçişte zaten güncellenmiştir; bu da i. öğenin daha önce dahil edilmiş olabileceği anlamına gelir. Tam olarak istediğimiz şey budur: i. öğe, zaten i. öğeyi içeren bir çözüme yeniden eklenebilir.
def unbounded_knapsack(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(w, W + 1): # iterate LEFT TO RIGHT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7)) # 9Madeni Para Değişimi II: Yolları Sayma
Madeni Para Değişimi II şunu sorar: Madeni para birimleri ve bir miktar verildiğinde, bu miktarı oluşturmanın farklı yollarının sayısını bulun (her madeni para sınırsız sayıda kullanılabilir). Bu, değeri en yükseğe çıkarmak yerine combinations saydığımız sınırsız sırt çantası türüdür. dp[c] değerini, c miktarını oluşturmanın yol sayısı olarak tanımlayın. Başlangıç durumu: dp[0] = 1 (0'ı oluşturmanın bir yolu vardır: hiçbir şey almamak).
Madeni Para Değişimi II Uygulaması
Her madeni para için miktarları soldan sağa gezin ve değerleri biriktirin: dp[c] += dp[c - coin]. dp[0] = 1 başlangıç durumu sayımı başlatır. Dış döngünün madeni paralar, iç döngünün ise miktarlar üzerinde olduğuna dikkat edin; bu, doğal olarak combinations sayımları verir (permutations vermez), çünkü her madeni para birimi dış döngüde tam olarak bir kez ele alınır.
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
print(change(5, [1, 2, 5])) # 4
print(change(3, [2])) # 0
print(change(10, [10])) # 1Combinations ve Permutations
Döngülerin sırası kritik önem taşır. Miktarı dış döngüye, madeni parayı iç döngüye koyarsak, permutations sayarız (sıra önemlidir). Madeni paralar [1,2] ve miktar=5 için 1+2+2 ile 2+1+2 ayrı sayılır. Madeni parayı dış döngüye koyarsak, combinations sayarız (sıra önemli değildir): 1+2+2 ile 2+1+2 aynı kabul edilir. Madeni Para Değişimi II combinations istediği için dış döngü madeni paralar üzerinde olmalıdır.
# Count COMBINATIONS (order does not matter) — coin outer loop
def combinations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins: # coin outer
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
# Count PERMUTATIONS (order matters) — amount outer loop
def permutations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for c in range(1, amount + 1): # amount outer
for coin in coins:
if c >= coin:
dp[c] += dp[c - coin]
return dp[amount]
print(combinations(5, [1,2,5])) # 4
print(permutations(5, [1,2,5])) # 13Çubuk Kesme Problemi
Bir başka klasik sınırsız sırt çantası problemi: Uzunluğu n olan bir çubuk ve 1'den n'e kadar her çubuk uzunluğu için fiyatlar verildiğinde, çubuğu en iyi biçimde keserek elde edilebilecek en yüksek geliri bulun. l uzunluğundaki her parça price[l] karşılığında satılabilir ve parçalar yeniden kullanılabilir (çubuk aynı uzunluktaki birden çok parçaya kesilebilir). Bu problem, W = n ve farklı kesim uzunluklarının öğeler olduğu sınırsız sırt çantasına doğrudan karşılık gelir.
def rod_cutting(prices, n):
# prices[i] = price of rod of length i+1
dp = [0] * (n + 1)
for length in range(1, n + 1): # each cut length
price = prices[length - 1]
for c in range(length, n + 1):
dp[c] = max(dp[c], dp[c - length] + price)
return dp[n]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(prices, 8)) # 22Madeni Para Değişimi I: En Az Madeni Para
Madeni Para Değişimi I (farklı bir problem), hedef miktarı oluşturmak için gereken en az madeni para sayısını bulmayı ister. Burada dp[c] = c miktarını oluşturmak için gereken en az madeni para sayısıdır. Yineleme bağıntısı: dp[c] = min(dp[c], dp[c - coin] + 1). dp[0] = 0 dışında tüm girişleri inf olarak başlatın. Bu problem de sınırsızdır (madeni paralar yeniden kullanılabilir); bu nedenle soldan sağa gezin. Sonuç sonluysa dp[amount] değerini, değilse -1 döndürün.
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coinChange([1,5,6,9], 11)) # 2 (5+6 or other combos)
print(coinChange([2], 3)) # -1Temel Fark: En Yükseğe Çıkarma, En Aza İndirme ve Sayma
Sınırsız sırt çantasının üç türü dp[c-coin] üzerinde farklı işlemler kullanır: Değeri en yükseğe çıkarma: dp[c] = max(dp[c], dp[c-w] + v); 0 olarak başlatılır. Maliyeti en aza indirme: dp[c] = min(dp[c], dp[c-coin] + 1); inf olarak başlatılır, dp[0]=0. Yolları sayma: dp[c] += dp[c-coin]; 0 olarak başlatılır, dp[0]=1. Hangi türün geçerli olduğunu ayırt etmek, mülakat problemlerindeki mücadelenin yarısıdır.
Karmaşıklık ve Mülakat İpuçları
Tüm sınırsız sırt çantası türleri, n öğe türü ve W hedef miktar olmak üzere O(n × W) zaman ve O(W) bellek kullanır. Madeni para problemlerinde n, madeni para birimlerinin sayısıdır. Mülakatlarda türü (en yükseğe çıkarma/en aza indirme/sayma) belirtin, 1B DP'yi yazın ve dış döngünün madeni paralar mı yoksa miktar mı üzerinde olduğu konusunda açık olun; değerlendiriciler bu ayrımın derin DP anlayışını sınadığını bilir.
Sınırsız Tür ile 0/1 Türünü Ayırt Etme
Hangi türün geçerli olduğunu belirlemek için şu işaretleri kullanın: sınırsız yeniden kullanım → sınırsız tür (ileri yönde gezinme); her öğenin tam olarak bir kez kullanılması → 0/1 türü (geriye doğru gezinme); problemde 'istenilen sayıda', 'sınırsız kaynak' veya 'yeniden kullanıma izin verilir' denmesi → sınırsız tür. Örnekler: madeni para değişimi, çubuk kesme, tam sayı bölme — hepsi sınırsız türdür. Alt küme toplamı, bölümlendirme, 0/1 sırt çantası — 0/1 türüdür. Bunu yanlış belirlemek, hata ayıklaması zor yanlış yanıtlara yol açar.
Tam Sayı Bölme ve Diğer Türler
Tam Sayı Bölme (LeetCode 343): Bir tam sayı olan n'yi, çarpımlarını en yükseğe çıkarmak için en az 2 pozitif tam sayıya bölün. Bu, 'öğelerin' 2'den n-1'e kadar olan tam sayılar olduğu sınırsız bir sırt çantası problemidir. dp[i] değerini, toplamı i olan tam sayıların elde edebileceği en yüksek çarpım olarak tanımlayın. 2'den i'ye kadar her j öğesi için dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Bu örnek, sınırsız örüntünün madeni para bağlamının ötesinde nasıl genellenebildiğini gösterir.
def integerBreak(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
return dp[n]
print(integerBreak(10)) # 36 (3+3+4 = 3*3*4 = 36)Kısa Sınama
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: sınırsız sırt çantası, öğelerin yeniden kullanılmasına izin vermek için kapasiteyi soldan sağa gezer, Madeni Para Değişimi II, dış döngüye madeni parayı koyarak combinations sayar ve üç tür — en yükseğe çıkarma, en aza indirme, sayma — yalnızca DP işlemi ve başlangıç değerleri bakımından farklıdır. Sırada, Eşit Alt Küme Toplamına Bölme problemini çözmek için 0/1 sırt çantasını kullanacağız.
Sıkça Sorulan Sorular
“Sınırsız Sırt Çantası ve Bozuk Para Değişimi II” dersi ücretsiz mi?
Evet — “Sınırsız Sırt Çantası ve Bozuk Para Değişimi II” 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 DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Sınırsız Sırt Çantası ve Bozuk Para Değişimi II” dersinde ne öğreneceğim?
Kapasiteyi ileri yönde yineleyerek öğelerin tekrar kullanılmasına izin verin; bu çeşitlemeyle bozuk para değişimi II’yi (yol sayısını sayma) ve çubuk kesme problemlerini çözün. DSA 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.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA 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.
“Sınırsız Sırt Çantası ve Bozuk Para Değişimi II” 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 DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA 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ı ve Alan Optimizasyonu
- Sınırsız Sırt Çantası ve Bozuk Para Değişimi II
- Eşit Toplamlı Bölüm Alt Kümesi
- Pozitif ve Negatif İşaretlerle Hedef Toplam