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:

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.

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.

Bu Yazıyı Paylaşın

« Veri Tanımlama Dili (Data Definition Language) | Açgözlü Yaklaşımı (Greedy Approach) »

Yorumlar

Giriş yaparak yorum yazabilirsiniz.

Bu Yazı Hakkında

bilgisayar.kavramlari.com üzerinde şu anda okumakta olduğunuz 'Torba Problemi (knapsack problem)' isimli yazı 24 Mar 2008 tarihinde, saat: 10:46 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 207 defa okunmuştur.

Benzer yazıları Bilgisayar Kavramları, Veri Güvenliği(Cryptography), algoritma analizi (teory of algorithms) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Eklenen Son Yazılar

Yapılan Son Yorumlar

hercumartesi: 777/10 mod23 işleminde takıldığım...
hercumartesi: 2P = R olarak gösterip s için (3xP^2 + a)...
Şadi Evren ŞEKER: Toplama işlemi sonucunda mod işlemi...
bazenvebazen: n q b b w derken n q p b w demek istedik?...
Şadi Evren ŞEKER: Tümleyeni terimini şu şekilde...

Bağlantılar

Shedai Net

SET Egitim

SES Hosting

SET Kurumsal