Knapsack Algoritması Nedir? Hırsız Çanta Problemi

Knapsack algoritması mevcut verilerden en optimum verimi alma üzerine kurulu bir algoritmadır.

Şöyle basitçe bir örnek vermek gerekirse bir hırsız düşünün sırt çantasına (knapsack) belirli bir ağırlığa kadar eşya koyabiliyor. Evde ise eşyaların ağırlıkları ve değerleri vardır, hırsız en optimum şekilde kar ile evden ayrılmalı ve çantasını ona göre doldurmalıdır.

Örnek:

Yukarıdaki tabloyu okumak gerekirse bize 4 adet eşya verilmiş. Bu 4 eşyanın ağırlıkları ve değerleri farklı. Bizim amacımız çantayı en pahalı eşyalarla doldurmak. Yükte hafif, pahada ağır eşyalar lazım. Çantanın kapasitesini de 5 kabul edelim. Aynı eşyayı kaç kere alabileceğimiz söyleniyor ancak söylenmezse sadece bir kere alabiliriz.

1 . Eşyanın ağırlığı 2, değeri 12.

2 . Eşyanın ağırlığı 1, değeri 10.

3 . Eşyanın ağırlığı 3, değeri 20.

4 . Eşyanın ağırlığı 2, değeri 15.

Hangi eşyanın daha değerli olduğunu değer/ağırlık formülünü uygulayarak bulabiliriz. Örneğin;

1. eşya 12/2=6$
2. eşya 10/1=10$
3. eşya 20/3=6,66$
4. eşya 15/2=7,5$

Bu durumda birim olarak değerlilik sıralaması eşya2>eşya4>eşya2>eşya1 olacaktır.

İlk olarak 1. eşyayı kontrol edeceğiz. Tabloda her iki tarafın da başına 0 koyarak başlamayı unutmayın. 1. eşyanın ağırlığı 2 imiş. Bu yüzden kapasite bölümünde 2’yi görene kadar 0 yazıyoruz. Kapasite bölümünde 2’yi gördük ve eşyanın kapasitesi de 2. Bu adımda eşyanın değerini yazıyoruz. Satırın sağ tarafına da 12$ yazmaya devam ediyoruz çünkü aynı eşyadan sadece bir kere alınabilir.

2.eşyaya geldiğimizde ise değerinin 1 olduğunu görüyoruz. Kapasite bölümünde 1 olan sütuna eşyanın değerini yazıyoruz, yani 10$. Kapasite 2 olunca bir önceki eşyayı kullanabiliriz. Daha ağır ancak fiyat olarak daha değerli. Bu yüzden 12$ yazıyoruz. Kapasite 3 olunca ise hem 1. hem de 2. eşyayı alabiliyoruz. Bu satırda en fazla 22$ değerinde eşya alabiliyoruz.

Not: Hangi eşyadaysanız o eşyadan önceki eşyaları kullanabilirsiniz. Örneğin 2. eşyada olan biri 1. eşyayı kullanabilir ancak 3. eşyayı kullanamaz. 

3. eşyaya geldiğimizde ise değerinin 20$ ve kapasitesinin 3 olduğunu görüyoruz. Kapasite bölümünde 1 olan sütuna 2. eşyanın değerini yazıyoruz. Kapasite bölümü 2 olan sütuna ise 1. eşyayı koyuyoruz. Üç olan kapasite sütununa ise 1 ve 2 numaralı eşyaları birlikte koyuyoruz çünkü değer olarak 3. eşyadan daha fazlalar. 1 ve 2. eşyanın toplam kapasitesi 3, değeri ise 22. 3. eşyanın kapasitesi 3, değeri 20. Bu yüzden tabloya 22 yazıyoruz. 4 numaralı kapasite bölümünde ise 2. ve 3. eşyaları kullanabiliriz. Kapasite olarak toplamda 4 yapıyorlar ve değerleri toplamı 30.

4. eşya ise kapasitesi 2 olduğu için 2. sütunda değişiyor. Birinci eşyayla aynı kapasitedeler ancak daha değerli. Bu yüzden tabloya 15 yazıyoruz. 3 numaralı kapasite bölümünde ise 2 ve 4 numaralı eşyaları alıyoruz, böylece tabloya 25 yazıyoruz. Diğer sütunlarda da hangi kombinasyonlar daha değerliyse onları alıyoruz. 5 numaralı kapasite bölümünde ise 1,2 ve 4 numaralı eşyaları alıyoruz ve değer 37 yapıyor.

Not: Genellikle tablonun sağ alt kısmı en büyük çıkar. Eğer tablonuzda sağ alt kısımdan daha büyük bir yer varsa, soruyu gözden geçirmenizde fayda var.