Sözlük · approach
Knapsack Problem
Bir kapasite kısıtı altında N aday öğeden alt-küme seçimi: her öğenin değeri ve ağırlığı verili; toplam ağırlık kapasiteyi aşmadan toplam değer maksimum. Ayrık optimizasyonun temel problemi.
Sırt Çantası ProblemiKnapsack Problem0/1 KnapsackBinary KnapsackMulti-Dimensional KnapsackMKP
Knapsack Problem (Sırt Çantası Problemi), N aday öğenin her birine değer (vᵢ) ve ağırlık (wᵢ) atfedilen, kapasite W altında Σwᵢxᵢ ≤ W ve max Σvᵢxᵢ olarak formüle edilen klasik ayrık optimizasyon problemidir; adı kapasiteli sırt çantasına en değerli yükü koyma metaforundan gelir. Pratik örnekler: sabit yıllık yatırım bütçesinde aday projelerden en yüksek NPV'li alt-küme seçimi, sabit pazarlama bütçesinde kampanya seçimi, kapasiteli kargo uçağına paket yükleme, fonun küçük-cap hisse seçimi. Varyantlar: 0/1 (binary; xᵢ ∈ {0, 1}), bounded (xᵢ ∈ {0, ..., cᵢ}), unbounded (xᵢ ≥ 0 tamsayı), multi-dimensional (MKP — m kısıt), quadratic (QKP — sinerji), multiple-choice (her gruptan bir öğe), subset-sum, knapsack with set-up. Knapsack NP-hard'dır ama Bellman (1957) dinamik programı O(N×W) zamanda **pseudo-polinom** çözüm sağlar — W küçük tutulduğunda (binler-on binler) milyon-öğe-ölçekli instance dakikalar içinde optimum. Branch-and-bound (Martello ve Toth 1990; Pisinger 1997 expanding-core), MIP, FPTAS (Ibarra ve Kim 1975 — (1-ε) garanti) klasik çözüm araçlarıdır. Kanonik kaynaklar: Dantzig (1957) ilk LP/IP çerçevesi, Martello ve Toth (1990) klasik kitap, Kellerer, Pferschy ve Pisinger (2004) modern kapsamlı kaynak. Portfolio Optimization (#018 Markowitz, sürekli ağırlık + varyans) ve Cutting Stock (#005, çok-boyutlu geometrik) yakın akrabalardır ama farklı problemlerdir.
Örnek
Orta-ölçekli holding CFO ofisi yıllık 200M TRY yatırım bütçesi ile 120 aday proje arasında 0/1 knapsack MIP modeli çözer; greedy 'NPV/yatırım sırala-seç' yaklaşımına kıyasla seçilen portföyün toplam NPV'si %8 daha yüksek olur, üç adet küçük-yatırım yüksek-getirili proje son TRY'lere sığar.