Sırt çantası problemi

Sırt çantası problemi (İngilizce: "knapsack problem") bir klasik yöneylem araştırması ve matematiksel olarak "kombinatorik optimizasyon" problemidir. Çözüm algoritması bakımından sırt çantası problemi en ünlü NP-hard problemleri arasındadır."Sırt çantası problemi"nin tanımlanması için şu notasyon kullanılmaktadır: İsimleri 1 ile n arasında sayı ile ifade edilen n değişik madde bulunur. Her bir madde i için değerinin vi ve ağırlığının wi olduğu bilinmektedir. Genel olarak her bir değer ve her bir ağırlık negatif olamazlar. Çanta içinde taşınabilecek tüm maddelerin toplam ağırlığının en çok W olup, bunun bir üst sınır olup aşılamayacağı bilinir.Bu problem tipi değişik sınırlama koşullarına göre değişik problem tipi şeklini alabilir. Bunlardan bazıları şöyle tanımlanabilir:"0-1 sırt çantası problemi": "Sırt çantası problem" tipleri arasında en iyi bilinen problem "0-1 sırt çantası problemi"dır. Bu tip problemde mevcut n maddeden her biri ya 1 birim olarak çantaya konulur yahut çantaya konulmaz, yani 0 birim çantaya koyulur. Her bir madde tek birim olarak çantaya konulur ya koyulmaz. Çantaya konulup konulmama, sadece 1 ve 0 değerleri alan "çantada mevcut olup olmama" adı verilebilen iki kategorili değer alan bir karar değişkeni olur. Böylece karar değiskeni olan xi ya 0 ya da 1 değeri alan iki kategorili "tam sayı değişkeni" olur. Matematik formülasyon şöyle verilir:"Sınırlı sırt çantası problemi": Bu tür problemde sırt çantası içine her maddeden birden fazla yerleştirilebilmek imkânı olduğu kabul edilir. Ama her bir madde için mevcut madde adedi sınırlıdır; i maddesi için mevcut sayı olan , 0 ile tam sayı olan  arasında olabilir. Bu tür "sınırlı sırt çantası problemi"nin matematik formülasyonu şöyledir: ."Sınırsız sırt çantası problemi": Bu tür problemde her madde sıfırdan sınırsız sayıya kadar sırt çantası içine yerleştirilebilir. i maddesi için sırt çantasına yerleştirilen sayı, yani , 0 ile tam sayı olan +∞ arasında olabilir.Bu şekildeki özel problem şu değişik şekilde de ifade edilebilir: bir negatif olmayan sayılar seti verilmiş ise, bunun herhangi bir altsetinin toplamı W toplam ağırlık/değer sınırına eşit olabilir mi?Buna benzer diğer bir özel problem, eğer her bir madde için negatif olan ağırlık mümkünse (yani −∞ < wi < +∞ ise) ve toplam ağırlık sınırı en çok W sıfıra eşit ise (yani W=0 olursa) ortaya çıkar. Problem şu olur: bir tam sayılar veri seti verilirse, bunun herhangi bir alt-seti tam olarak 0a eşit olabilir mi? Buna "alt-set toplamı problemi" adı verilir. Kriptografi alanında sırt-çantası problemi" ismi sadece bu çok özel "alt-set toplam∞ problemi" olarak görülür.Eğer tek bir değil ama birden fazla sırt-çantası yüklemek mümkün ise, bu yeni tip probleme "kutu paketleme problemi" adı verilir.Konu bilgisayar bilimi bakış açısından ele alınırsa "sırt-çantası problemi" şu nedenler dolayısıyla ilgi çekmektedir:"Sözde-polinomsal zamanda" çözümü sağlayan algoritmaları bir alt-program olarak kullanan "FPTAS yaklaşık tam polinomsal zaman kullanma" yordamı ile çözüm bulunmak imkân dahilindedir.Tam olarak çözüm için problem NP-tam karakterlidir ve her türlü halde hem hatasız hem de hızlı polinomsal zamanda çözme algoritması bulmak imkânsızdır.Pratikte, buna rağmen birçok halde ve bazı dağılımlardan bazı rastgele haller'' verileri kullanılarak pek çok sayıda problem için tam şekilde çözüm yapma için kullanma imkânı bulunmaktadır"Alt-set toplamı" versiyonu şekildeki sırt-çantası problemi, genellikle, "Karp'in 21 NP-tam problemler"inden biri olduğu bilinmektedir.Araştırma kaynaklarında ilgi çeken bir konu sırt-çantası probleminin "zor" şekillerinin nasıl görünüş alacağını tespit etmeye çalışmak olmuştur. Bu yaklaşımla NP-tam tavırlı en-fena halleri tespit edip bunları daha kolay uygulanır şekillere koyma imkânları araştırılmıştır.Sırt-çantası problemlerini çözümlemek için parasız kullanılmaları imkânı olan birkaç tane algoritma yazılımı hazır bulunmaktadır. Bunlardan seçilmişleri şu listede verilir:PYAsUKP: Sinirsiz Sirt Cantasi Problemi Icin Bir Diger Cozucu, yazilim kodlari, sinama sonuclar ve bazi onemli makaleler.  (Erişim:5.6.2010).Home page of David Pisinger with downloadable copies of some papers on the publication list (including  "Where are the hard knapsack problems?")  (Erişim:5.6.2010).