Sırt Çantası Problemi (Knapsack): "Hangi Eşyaları Alayım?" Sorusunun NP-Zor Matematiği

Bir hırsız geceyarısı bir mücevher mağazasına girdi. Yanında bir sırt çantası var; en fazla 50 kg taşıyabilir. Mağazada farklı ağırlıkta ve farklı değerde eşyalar var:

Eşya	Ağırlık (kg)	Değer (₺)
Altın külçe	30	50.000
Gümüş kase	20	25.000
Yakut yüzük	5	30.000
Antika saat	15	40.000
Madeni para	10	18.000

Hangi eşyaları alırsa toplam değeri maksimum olur?

Bu, klasik sırt çantası problemi (knapsack problem). Görünüşte sade — sadece bir kombinasyon seçimi — ama matematiksel olarak çok zengin. Modern bilgisayar biliminin en sevilen örneklerinden biri; dinamik programlama, NP-zorluk, yaklaşık algoritmalar gibi kavramların öğretiminde kullanılır.

Sıra dışı zorluk

İlk bakışta: "en değerliyi al, taşıyabildiğim kadar" diyebilirsiniz. Ama bu strateji yanlış sonuçlara götürebilir.

Yukarıdaki örneği bu açgözlü stratejiyle çözelim. En yüksek değer/ağırlık oranlı eşyayı önce alalım:

• Yakut yüzük: 30000/5 = 6000 ₺/kg
• Antika saat: 40000/15 = 2667 ₺/kg
• Altın külçe: 50000/30 = 1667 ₺/kg
• Madeni para: 18000/10 = 1800 ₺/kg
• Gümüş kase: 25000/20 = 1250 ₺/kg

Açgözlü sıra: Yakut (5kg) → Madeni para (10kg) → Antika saat (15kg) → Altın külçe... ama 30+15+10+5 = 60kg, sınırı aşıyor. Saat'ten önce duruyoruz; veya saat yerine başka şey deniyoruz...

Görüyorsunuz, doğru kombinasyonu bulmak için kombinasyon denemek gerekiyor. $n$ eşya için $2^n$ olası kombinasyon. 5 eşya için 32 kombinasyon — elle çözülebilir. Ama 30 eşya için $2^{30} \approx 10^9$ kombinasyon — modern bir bilgisayar bile saatler harcar. 100 eşya için $2^{100} \approx 10^{30}$ — evrenin yaşına yetmez.

Dinamik programlama çözümü

Bu kombinatorik patlama yerine, dinamik programlama (DP) tekniği çok daha verimli bir çözüm sunar.

Fikir: bir tablo oluştur. Satırlar eşyaları, sütunlar kapasite değerlerini (0'dan W'ye) temsil eder. Her hücre $\text{table}[i][w]$, "ilk $i$ eşyadan $w$ kapasiteli sırt çantasına sığacak maksimum değer" sorusuna cevap verir.

Yineleme:

$\text{table}[i][w] = \max(\text{table}[i-1][w],\ \text{table}[i-1][w - \text{wt}[i]] + \text{val}[i])$

Yani her eşya için iki seçenek var: almak ya da almamak. İki seçeneğin daha iyisini al.

Bu algoritma $O(nW)$ zamanda çalışır — $n$ eşya sayısı, $W$ kapasite. 100 eşya ve 1000 kapasite için $10^5$ işlem — anlık.

"Sözde polinom zaman"

Burada ilginç bir matematik incelik var. Dinamik programlama çözümü $O(nW)$ olduğu için, "polinom zamanlı" gibi görünür. Ama dikkat: $W$, kapasitenin kendisidir; bit sayısı değil. Eğer $W = 10^{18}$ ise, "polinom zaman" $10^{18}$ işlem demektir.

Modern karmaşıklık teorisinde, "polinom zaman" girdi büyüklüğüne göre tanımlanır — yani $W$'nin bit sayısı $\log W$'ye göre. Bu açıdan, knapsack çözümü $O(n \cdot 2^{\log W})$ = $O(n W)$, ama $\log W$ açısından üsteldir. Yani knapsack, sözde polinom (pseudo-polynomial) zaman algoritmaya sahip ama gerçek anlamda polinom değil.

Bu hassas matematik farkı, knapsack'in NP-zor olarak sınıflandırılmasının sebebi. Modern bilgisayar biliminin teorik temellerinden biri.

NP-zor doğası

Sırt çantası problemi, karar problemi olarak ifade edildiğinde NP-tam sınıfındadır:

"Ağırlık toplamı $\le W$ ve değer toplamı $\ge V$ olan bir eşya altkümesi var mı?"

Bu, Karp'ın 1972'deki 21 klasik NP-tam problemleri listesinde yer alır. NP-tam olmak demek: eğer polinom zamanlı bir tam çözüm bulunsa, $P = NP$ olur (bilgisayar bilimi tarihinin en büyük açık problemini çözer).

Hiç kimse böyle bir algoritma bulamadığı için, modern uygulamalar yaklaşık algoritmalar ve heuristik yöntemler kullanır.

Yaklaşık algoritmalar

Knapsack için pratik yaklaşık çözümler:

FPTAS (Fully Polynomial-Time Approximation Scheme)

İstediğiniz hassasiyet $\epsilon$ için, polinom zamanda $(1-\epsilon)$ oranlı çözüm garantili. Yani gerçek optimumdan en fazla %5 sapma ile çözüm bulmak için polinom zamanda algoritma var. Bu çok güçlü bir teorik sonuçtur ve knapsack'i NP-zor problemler içinde "daha nazik" yapan özelliktir.

Genetik algoritmalar

Doğal seleksiyon prensiplerini taklit eden algoritmalar; büyük knapsack örnekleri için yaygın kullanılır.

Tavlama benzetimi (Simulated annealing)

Termodinamiğin enerji minimizasyonundan esinlenen heuristik. Büyük endüstriyel knapsack problemleri için pratik.

Modern uygulamalar

Sırt çantası problemi, modern dünyada şaşırtıcı kadar çok yerde:

1. Kaynak tahsisi (resource allocation)

Bir şirketin sınırlı bütçesi var; farklı projelere yatırım yapmak istiyor. Her projenin maliyeti ve beklenen getirisi var. Hangi projeleri seçer? — Sırt çantası problemi.

2. Yatırım portföyü

Sınırlı sermaye, farklı hisse senetleri, her birinin maliyet ve beklenen getirisi. Hangi hisseler? — Sırt çantası varyantı.

3. Veri merkezleri (cloud computing)

Bir sunucunun sınırlı CPU/RAM kapasitesi var; farklı görevler ya da müşteriler arasında nasıl dağıtılır? — Çok boyutlu knapsack.

4. Yük taşımacılığı

Bir kamyon ya da gemi sınırlı kapasitede; hangi paketler taşınır? — Knapsack.

5. Reklamcılık

Sınırlı ekran alanı (mobil, web), farklı reklamlar farklı değer ve boyutta. Hangi reklamlar gösterilir? — Online knapsack varyantları.

6. Kriptografi (tarihsel)

1978'de Ralph Merkle ve Martin Hellman, knapsack tabanlı bir açık anahtarlı şifreleme sistemi önerdi (Merkle-Hellman knapsack cryptosystem). Birkaç yıl sonra Adi Shamir tarafından kırıldı — ama hâlâ bir tarihsel önemli denemedir.

7. Bilgisayar oyunları

Envanter yönetimi, beceri ağaçları, kaynak optimizasyonu — pek çok strateji oyununda gizli knapsack hesabı var.

8. Genetik dizilim

Bazı bioinformatik problemler (örneğin restriksiyon enzim yerleri seçmek) knapsack benzeri formülasyonlara dönüşür.

Knapsack'in matematiksel zenginliği

Klasik sırt çantasının pek çok varyantı vardır:

• 0/1 Knapsack: Her eşya ya alınır ya alınmaz (klasik form).
• Fractional (sürekli) knapsack: Eşyalar parçalı alınabilir. Bu polinom zamanda çözülür (greedy strateji çalışır).
• Bounded knapsack: Her eşyadan en fazla belirli sayıda alınabilir.
• Unbounded knapsack: Her eşyadan istediğin kadar alabilirsin.
• Multi-dimensional knapsack: Birden fazla kısıt (ağırlık + hacim).
• Multiple choice knapsack: Eşyalar gruplara ayrılmış; her gruptan sadece bir eşya seçilebilir.
• Quadratic knapsack: Eşyaların değerleri etkileşimli (bazı çiftler bonus verir).

Her varyantın kendine özgü matematiksel zorlukları ve çözüm yöntemleri vardır. Modern operasyon araştırması, bu varyantların yüzlerce makalesini içerir.

Tarihsel arka plan

Sırt çantası probleminin formal matematiksel formülasyonu George Dantzig'in 1957'deki çalışmalarına dayanır. Dantzig, lineer programlamanın da öncüsü (Simpleks algoritması). Knapsack'in NP-zor olduğu, 1972'de Richard Karp tarafından "Reducibility Among Combinatorial Problems" makalesinde kanıtlandı.

İsim "sırt çantası" 1897'deki bir matematik problem koleksiyonundan gelir (Tobias Dantzig'in babası Vasily Dantzig, kısmen aile bağlantısı).

Bir hayat dersi

Sırt çantası problemi, "sade görünen sorular matematiksel olarak şaşırtıcı zorlukta olabilir" gerçeğinin güzel bir örneğidir. Bir hırsızın ne çalacağına karar vermesi — modern operasyon araştırması, bulut bilgi işlem, finansal portföy yönetimi, hatta evrim biyolojisinin matematik temelidir.

Daha geniş bir hayat dersi: kombinasyonel karar problemleri, hayatın her yerinde. Hangi projeyi başlatacaksın, hangi öğrenciyi alacaksın, hangi yatırımı yapacaksın — her birinin altında bir tür sırt çantası matematiği yatar. Bu matematik genelde "bir tam çözüm yok" der; ama "iyi yaklaşık çözüm" verir.

Bir sonraki sefer bir tatil çantanızı toplarken — "bu kıyafet mi, kitap mı?" diye düşünürken — modern matematik tarihinde bu basit problemin trilyon dolarlık endüstrilerin matematik temeli olduğunu hatırlayabilirsiniz. Knapsack, hayatın günlük kararlarıyla modern teorik bilgisayar bilimi arasındaki gizli köprü.