knapsack problem

• bir hırsızın sınırlı yere sahip çantasına farklı değerdeki ve boyuttaki mücevherleri nasıl koyması gerektiğini çözen dynamic programmingin has örneği algoritma
  
  ^*...ile çözülen problem
• iki farkli versiyonu bulunmakla beraber kurgu soyledir:
  
  hirsizin birisi iceride n adet urunun oldugu bir magazaya girer. i'nci urunun degeri vi (value i), agirligi ise wi(weight i) seklinde gosterilmektedir. hirsizin en fazla m kg alabilen bir cantasi var ise bu soygundan kaldirabilecegi urunlerinin degeri en fazla ne olabilir?
  
  ilk versiyonda: urunler parcalanamaz; i, w ve m tam sayidir (misal magazada farkli madenlerden kulceler var ve bolunemezler)
  
  ikinci versiyonda (fractional knapsack problem); degerler tam sayi degildir urunun bir kismini almayi secebilir hirsiz. (farkli madenlerin tozlari var cuvallar icinde, cuvalin tamamini almak yerine istedigi kadar toz alabilir icinden)
  
  (bkz: dynamic programming)
• bir versyonunda daga tirmanacak bir dagci vardir ve sirt cantasini kendisine en fazla yarari saglayacak ekipmanla doldurmasi gerekir. her alet/edevatin belli bir agirligi ve dagciya sagladigi fayda vardir. gerisi bildigimiz integer programming.
• bir başka versiyonu da şöyledir:
  
  bir bombardıman uçağı 8 adet bomba taşıyabilmektedir. bombalanacak hedeflerin yerleri ve herbirinin düşmana vereceği zarar birbirinden farklıdır. uçağın belirli bir menzili olduğunu da düşünerek düşmana verilecek hasarı enbüyükleyecek çözümü bulunuz. buldurunuz. bi buldurun be.
  
  (bkz: yöneylem araştırması)
  (bkz: ikinci dünya savaşı)
• aslen 8. yüzyilda ünlü matematikci el harezmi tarafindan "n'apsak" adiyda ortaya konmus olup doguya ait sahip cikilmayan her deger gibi bati tarafindan knapsack problem adiyla kendilerine mal edilmistir.
• populer bir np-complete problem.
• "knapsack problem" ya da daha az bilinen ismiyle "rucksack problem", bilgisayar bilimlerinde optimizasyon algoritmalarının tanıtımına giriş yaparken örnek olarak kullanılan bir problemdir ve iki farklı türü bulunmaktadır.
  
  bunlardan ilki ve daha zorlayıcı olanı "0/1 knapsack problem" olarak bilinir. bu versiyonda elinde torbası ile değişik ağırlıkta değerli eşyaların bulunduğu bir eve giren bir hırsız konu edilir. hırsızımız elini çabuk tutmak ve toplamda olabildiğince yüksek değerli eşya ile evden ayrılmak zorundadır. ancak evdeki değerli eşyaların her biri farklı ağırlıkta ve değerde iken hırsızımızın torbası ile taşıyabileceği şeylerin bir sınırı vardır. 300$'lık ve 20kg'lık bir eşyadan ise her biri 200$'lık ve 10kg'lık iki eşyayı almak daha mantıklı bir tercih ve hemen akla gelecek bir yöntemdir. eşya sayısı az iken bu şekilde seçim yapmak kolay olmasına rağmen bu sayı arttıkça bütün kombinasyonları göz önüne almak imkansız bir hale gelecek ve "mutlak optimum" tercihi bulana kadar hırsızımız yakayı ele verecektir.
  
  işte bu noktada devreye "greedy algorithm" gibi optimizasyon algoritmaları ve "dynamic programming" gibi konuya farklı bakış açıları girer. hırsızımız bütün olasılıkları deneyerek en verimli tercihi bulmakla uğraşacağına problemi aşama aşama ele alıp belirlediği bir kriter üzerinden kökten uca doğru çözmeyi deneyebilir. örneğin eşyaları değer/ağırlık oranına göre sıralayıp en yüksekten en küçük oranlı olana doğru sırasıyla çantasına atabilir ve çantasında yer kalmadığında durarak zamandan kazanabilir. görülebileceği gibi bu tarz bir yaklaşım çoğu zaman en iyi sonucu vermez ancak çok yüksek bir hızla tatmin edici doğrulukta bir sonuca ulaşmamızı sağlar. bu tarz algoritmalara ve ulaştığımız sonuçlara "heuristic" yani "sezgisel" ismi verilir, pratik kullanımları hayat kurtarıcı olsa da mutlak doğruluk gerektiren (matematiksel ispatlar gibi) alanlarda kendilerinden uzak durmak gerekir.
  
  problemin diğer versiyonu ise "continuous knapsack problem", "fractional knapsack problem", "unbound knapsack problem" gibi pek çok farklı isimle bilinir. bu durumda hırsızımız ilkinden farklı olarak torbasına istediği şeyden istediği miktarda koyabilecektir. bunu daha iyi anlamak için değerli eşyaları değerli tozlar ile değiştirebiliriz. yaptığımız bu değişiklik kullandığımız algoritmaların sonuçlarının doğruluğuna etki edecektir. problemin bu versiyonunda ilkinin aksine optimizasyon algoritmaları bizi mutlak optimum seçime ulaştırmaktadır. örneğin altın tozlarını çantasına dolduran hırsızımız bu toz bittikten sonra gümüş tozuna geçecek o bittikten sonra diğer değerli toza ve bu durum çantasında yer kalmayana kadar devam edecektir. böylece (çantada boşta yer kalmadığı için) optimum sonuçtan sapma da gerçekleşmeyecektir.
  
  (bkz: greedy algorithm)
  (bkz: dynamic programming)
  (bkz: heuristic)
  
  wikipedia linki
• ilk ortaya çıkış nedenini merak ettiğim problem. aynı zamanda yarınki sınavıma soru olacak konulardan biri olan problem. genelde hırsız örneği ile anımsanmasına rağmen değişik örnekleri de mevcuttur.
• güzel türkçemizde "yükte hafif pahada ağır" tabiriyle betimleyegeldiğimiz neyi alsam neyi bıraksam sorunsalı.
  
  .
• eve giderken götürmem gereken onlarca eşyamı minnacık sırt çantama sığdırarak kendimce en zor olanını çözdüğüm problem türü. kapasite sınırını aşmış olabilirim o ayrı.