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ı pi olsun ve her eşyanın ağırlığı ai 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:

Torba Problemi (knapsack problem)

Bu modelde görüldüğü üzere, xi 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 ci=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:

knapsack Torba problemi

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 bi ile gösterilen ve bir üründen en fazla alınabilen değerdir. Toplamda en fazla alabileceğimiz değer ise hala ci‘dir. Bu problem tipinde her üründen alınan miktar ise değişmektedir ve bu miktar xi ile gösterilir.

Örneğin yukarıdaki problemin çözümünde 1kg portakal fileye konulacaksa, bu durumda x4 = 1, b4 = 5 , p4 = 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.

Tagged:

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Sanırım size cevap yazarken, neden böyle düşündüğünüzü anladım. Buradaki tanımda bulunan i değeri 0

  2. Şadi Evren ŞEKER Article Author

    Mehmet Sinan Beyin mesajı üzerine, yazıda gerekli düzeltmeleri yaptım ve ufak iki örnek ekledim. Umarım daha anlaşılır olmuştur. Yine de anlaşılmıyorsa lütfen mesaj atınız.

    Teşekkürler

  3. mehmet sinan

    …………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ı pi olsun ve…..

    düzeltme yaparken sanırım bir yanlışlık oluşmuş. Ama ben anladım teşekkür ederim.

  4. faruk yılmaz

    Öncelikle selamlar …
    Bir sorum olcaktı
    elimizde bu ürünler var ama 2 tanede (veya daha fazla) farklı kapasitede torba varsa mantık nasıl kurulur…

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir