Torba Problemi (knapsack problem)

Yazan: Şadi Evren ŞEKER

Torba problemi basitçe bir torbanın içerisine en fazla eşyanın yerleştirilmesini hedefler. Problem hırsız örneğinden daha iyi anlaşılabilir. Buna göre bir hırsız çantasına ağırlıkça en az, pâhâca en çok eşyayı doldurmak ister. Bu durumda her eşyanın

Aşağıdaki her özel problem durumu için eşyaların pahası p_i olsun ve her eşyanın ağırlığı a_i olsun. Çantanın taşıyabileceği azamî kapasite de ci olarak tanımlansın.

0-1 Torbla problemi: Bu problem tipinde eşyalar ya tamamen alınır ya da tamamen bırakılır. Alınacak olan eşyanın bir kısmını almak mümkün değildir. Dolayısıyla bir eşyanın alınıp alınmamasını xi ile gösterecek olursak problem aşağıdaki şekilde modellenebilir:

Bu modelde görüldüğü üzere, x_i değeri, 0 veya 1 olabilmektedir. 0 olması durumunda i elemanından alınmıyor 1 olduğunda ise i elemanının tamamı alınıyor demektir.

Örnek

Elimizde aşağıdaki eşyalar bulunsun:

1. saat, 0.2 kg  100TL

2. fotoğraf makinesi 0.5kg 300TL

3. kamera 0.7kg  700TL

4. cep telefonu 0.3kg 500TL

5. anahtar 0.1kg 10TL

Şimdi problemimiz, elimizdeki bir torbaya (örneğin 1kg kapasiteli) yukarıdaki eşyaları en fazla para edicek şekilde yerleştirmek istememiz.

bu durumda c_i=1kg olarak tanımlamış oluyoruz.

Çözümde ise i = { 3,4} kümesi alınıyor. Yani kamera ve cep telefonunu aldığımızda 1200 TL ile en pahalı ve torbamıza sığan kümeyi almış oluyoruz.

Sınırlı Torba Problemi (Bounded Knapsack Problem): Bu problem tipinde ise her eşyadan alınabilecek miktarda sınır vardır. Bu problemin modeli aşağıda verilmiştir:

Sınırsız Torba Problemi (Unbounded Knapsack Problem): Bir önceki sınırsız torba probleminden farklı olarak bu problemde alınabilecek malzemelerin herhangi bir sınırı bulunmamaktadır.

Örnek

Bu problem tipinde ise örneğimizi değiştirmemiz gerekiyor.

1. elma 2TL , 4kg

2. armut 5TL, 3kg

3. kiraz 4TL, 6kg

4. portakal 3.5TL, 5kg

şeklinde verilen ürünlerden örneğin 10kg’lık bir fileye en pahalı nasıl bir seçim yapılmalıdır sorusu sorulabilir.

Bu durumda her üründen değişk miktarlarda var. Örneğin en fazla 4kg elma alabiliyoruz bu değer modelimizdeki b_i ile gösterilen ve bir üründen en fazla alınabilen değerdir. Toplamda en fazla alabileceğimiz değer ise hala c_i‘dir. Bu problem tipinde her üründen alınan miktar ise değişmektedir ve bu miktar x_i ile gösterilir.

Örneğin yukarıdaki problemin çözümünde 1kg portakal fileye konulacaksa, bu durumda x₄ = 1, b₄ = 5 , p₄ = 3.5 olarak alınmalıdır.

Torba problemi, veri güvenliği (cryptography) konusunda genellikle alt küme toplam problemi olarak kullanılır ve örneğin merkle-hellman yönteminde bu özelliğinden faydalanılır.

Torba problemi aynı zamanda dinamik programlama (dynamic programming) için de oldukça elverişli bir problemdir ve aşağıdaki yaklaşımla çözülebilir:

Troba probleminin bir diğer çözüm önerisi açgözlü yaklaşımı (greedy approach) iledir. Bu çözüme göre alınabilecek en yüksek meblağdaki eşya torbaya doldurularak her seferinde kalan yer için mümkün olan en değerli eşya aranır. En sonunda yer kalmayana veya kalan yere bir eşya konulamayana kadar bu şekilde gidilir.

Açgözlü yaklaşımının (greedy approach) bir dez avantajı her zaman en verimli sonucu üretememesidir.