Coding Interview Prep · Ders

0/1 Sırt Çantası ve Alan Optimizasyonu

Q: “0/1 Sırt Çantası ve Alan Optimizasyonu” dersi ücretsiz mi?

Evet — “0/1 Sırt Çantası ve Alan Optimizasyonu” 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.

Q: 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 1. dersidir.

Q: “0/1 Sırt Çantası ve Alan Optimizasyonu” 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.

Q: 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.

0/1 sırt çantası bağıntısını çıkarın, 2B tabloyu doldurun ve kapasiteyi tersten yineleyerek tabloyu 1B diziye indirgeyin.

0/1 Sırt Çantası ve Alan Optimizasyonu, CoddyKit'te ücretsiz bir Coding Interview Prep 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, 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.

0/1 Sırt Çantası Problemi

0/1 Sırt Çantası problemi şudur: Her birinin w[i] ağırlığı ve v[i] değeri olan n öğe ile kapasitesi W olan bir sırt çantası verildiğinde, kapasiteyi aşmadan toplam değeri en yükseğe çıkarmak için öğeleri seçin. Her öğe tam olarak bir kez alınır (0 = atla, 1 = al). Bu problem, eşit toplamlı alt kümelere bölme ve hedef toplam gibi çok sayıda mülakat DP probleminin temel örneğidir.

DP Durumu ve Yineleme Bağıntısı

dp[i][c] değerini, kapasitesi c olan ve ilk i öğenin kullanılabildiği durumda elde edilebilecek en yüksek değer olarak tanımlayın. i. öğe için iki seçenek vardır: öğeyi atlamak (dp[i-1][c]) veya w[i] <= c ise öğeyi almak (dp[i-1][c-w[i]] + v[i]). Yineleme bağıntısı şöyledir: w[i] <= c olduğunda dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]); aksi takdirde dp[i][c] = dp[i-1][c]. Başlangıç durumu: tüm c değerleri için dp[0][c] = 0.

2B DP Tablosu Uygulaması

2B tabloda (n+1) x (W+1) giriş bulunur ve her öğe için satırlar sırayla doldurulur. Tüm satırlar doldurulduktan sonra dp[n][W] en yüksek değeri içerir. Bu işlem O(n × W) zaman ve O(n × W) bellek kullanır; bu, W küçük olduğunda verimli olan sözde polinomsal bir karmaşıklıktır.

def knapsack_2d(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
        w, v = weights[i-1], values[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]  # skip item i
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    
    return dp[n][W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8))  # 10

1B DP için Kapasiteyi Neden Ters Yönde Gezmek Gerekir

Temel gözlem şudur: i. satır yalnızca i-1. satıra bağlıdır. Bu nedenle tek bir 1B dizi kullanıp değerleri yerinde güncelleyebiliriz. Ancak kapasiteyi c için soldan sağa (küçükten büyüğe) gezersek, i. öğe iki kez sayılabilir; çünkü i. öğeyi zaten içeren, c-w[i] için güncellenmiş değeri kullanabiliriz. Sağdan sola (büyükten küçüğe) gezmek, her öğenin her satır güncellemesinde en fazla bir kez kullanılmasını sağlar.

# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
#     dp[c] = max(dp[c], dp[c-w] + v)   <-- dp[c-w] may already use item i

# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
#     dp[c] = max(dp[c], dp[c-w] + v)   <-- dp[c-w] still from previous row

1B Bellek Optimizasyonlu Uygulama

Yalnızca bir dizi tutup kapasiteyi W'den w[i]'ye doğru geriye sayarak 2B tabloyla aynı sonucu O(W) bellek kullanarak elde ederiz. Zaman karmaşıklığı O(n × W) olarak kalır. Bu bellek optimizasyonunu akılda tutmak çok önemlidir; görüşmeciler sizden 2B sırt çantasını 1B'ye indirmenizi sıkça ister.

def knapsack_1d(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, -1):  # iterate RIGHT TO LEFT
            dp[c] = max(dp[c], dp[c - w] + v)
    
    return dp[W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8))  # 10

Seçilen Öğeleri Yeniden Oluşturma

Hangi öğelerin selected olduğunu bulmak için tam 2B tabloya ihtiyacınız vardır. Tabloyu doldurduktan sonra dp[n][W] konumundan başlayıp geriye doğru izleyin: dp[i][c] != dp[i-1][c] ise i. öğe dahil edilmiştir; ağırlığını c'den çıkarıp i-1. satıra geçin. i = 0 olana kadar devam edin. 1B optimizasyonu bu yeniden oluşturma olanağını ortadan kaldırır.

def knapsack_with_items(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        w, v = weights[i-1], values[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    
    # Reconstruct
    selected, c = [], W
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i-1][c]:
            selected.append(i-1)
            c -= weights[i-1]
    return dp[n][W], selected[::-1]

print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))

Uygulamalı Örnek: Toplam Değeri En Yükseğe Çıkarma

Şu öğeleri ele alalım: weights=[2,3,4,5], values=[3,4,5,6], W=8. En iyi seçim, ağırlığı 3 (değeri 4) ve ağırlığı 5 (değeri 6) olan öğeleri almaktır; toplam ağırlık 8, toplam değer 10 olur. Ağırlığı 2 ve 5 olan öğeler alınırsa toplam değer 9, ağırlığı 2 ve 3 olanlar alınırsa değer 7 olur. DP, 10 olan en yüksek değeri doğru biçimde bulur. Açgözlü yaklaşımın (en yüksek değer/ağırlık oranını seçmenin) önce oranı 1.5 olan öğeyi (ağırlık 2, değer 3) seçeceğine dikkat edin; bu seçim her zaman en iyi değildir.

Kesirli Sırt Çantası ve 0/1 Sırt Çantası

Kesirli Sırt Çantası probleminde öğelerin kesirlerini alabilirsiniz. Bu problem, değer/ağırlık oranına göre sıralama yapılarak açgözlü yöntemle çözülebilir. 0/1 Sırt Çantası probleminde öğeler bölünemez; bu nedenle açgözlü yöntem başarısız olur ve DP gerekir. Görüşmeciler bu ayrımı, açgözlü yöntemin ne zaman uygulanabileceğini bilip bilmediğinizi sınamak için kullanır. Kesirli tür sorulursa hemen sıralamalı açgözlü yöntemden, 0/1 tür sorulursa DP'den söz edin.

# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
    items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
    total = 0
    for v, w in items:
        if W >= w:
            total += v; W -= w
        else:
            total += v * (W / w); break
    return total

print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))

Sözde Polinomsal Zaman Karmaşıklığı

0/1 Sırt Çantası NP-tam olmasına rağmen onu O(nW) zamanda çözeriz. Çelişki şu nedenle ortadan kalkar: O(nW) sözde polinomsaldır; W, girdi boyutu değil, bir değerdir. W'nin ikili gösterimi O(log W) bit tutar; dolayısıyla gerçek karmaşıklık O(n × 2^(log W)) olur ve bu, girdi boyutuna göre üstel bir karmaşıklıktır. W küçük olduğunda (örneğin 10⁴) DP uygulanabilirdir; W 10⁹ olabildiğinde farklı yaklaşımlara ihtiyaç duyarız.

Görüşmecinin Takip Sorusu: Büyük Kapasite

Görüşmeci W değerini çok büyük (örneğin 10⁹), ancak n değerini küçük olarak sınırlandırırsa standart DP yetersiz kalır. Alternatifler şunlardır: (1) O(2^(n/2) × n) zamanda ortadan buluşma, (2) kesirli tür için açgözlü yaklaştırma veya (3) dallan ve sınırla yöntemi. W <= 10⁵ olan çoğu mülakat probleminde beklenen yanıt, geriye doğru gezinen 1B DP'dir.

Büyük Kapasite için Ortadan Buluşma

W çok büyük, ancak n küçük olduğunda (örneğin n=40), standart O(nW) DP uygulanamaz; kaba kuvvetle 2^n alt kümesini denemek ise çok yavaştır. Ortadan buluşma, öğeleri iki yarıya böler, her yarı için 2^(n/2) alt kümesinin tamamını listeler ve bunları en iyi biçimde eşleştirir. Yarılardan birini ağırlığa göre sıralayın; ardından diğer yarıdaki her alt küme için, kapasite dahilindeki en iyi eşleşmeyi ikili aramayla bulun. Bu yöntem O(2^(n/2) × n) zamanda çalışır ve n 40'a kadar uygulanabilirdir.

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: 0/1 sırt çantası DP'sinde dp[i][c] durumu, i öğe ve c kapasite ile elde edilebilecek en yüksek değeri temsil eder, yineleme bağıntısı her öğeyi atlamayı veya almayı seçer ve 1B bellek optimizasyonu, öğelerin iki kez sayılmasını önlemek için kapasiteyi sağdan sola gezer. Sırada, öğelerin yeniden kullanılabildiği sınırsız sırt çantasını inceleyecek ve bunu Madeni Para Değişimi II'ye uygulayacağız.

Sıkça Sorulan Sorular