0 00
Sırt çantası (torba) problemi (knapsack problem) nedir?

Bir çanta(ya da sınırlı kapasiteli herhangi bir alan), en değerli (ya da faydalı) eşyalarla nasıl doldurulur, sorusuna sırt çantası ya da torba problemi denir.

Sırt çantası problemi
Sırt çantası ya da bilinen diğer adıyla torba problemi (knapsack problem), bir optimizasyon problemidir.

Problemin tanımı şöyledir:
 
Ağırlıkları (w) ve değeri/katkısı (v) bilinen n tane nesne, kapasitesi W olan bir çantaya koyulacaktır.

Çantayı kapasitesini aşmayacak şekilde en değerli olan nesnelerle doldurmak için nesnelerden hangileri çantaya koyulmalıdır.

Kaynak tahsisi
Sırt çantası problemi en iyi seçimi yapma problemlerinin genel adıdır. Bu problem kaynak tahsis etme (resource allocation) problemi olarak genişletilebilir.

Bu durumda problem şöyle tanımlanır:
Sınırlı kapasiteli bir kaynak kullanılarak, amaç fonksiyonunu maksimize edecek şekilde kaynakların tahsis edilmesi.

Problemi daha iyi anlamak için aşağıdaki örnekleri inceleyiniz:
  • Bir dağcı çantasına hangi malzemeleri koymalıdır?
  • Bir hırsız soygun esnasında çantasına hangi eşyaları koymalıdır?
  • Bir kargo uçağı ile taşınacak yükler nasıl seçilmelidir?
Amaç
Amaç, çantanın değerini en fazla yapacak (Vmax, maksimize edecek) objeleri seçmektir. Başka bir deyişle hafif ama pahada ağır nesnelerin seçilmesidir.

Türleri
Sırt çantası probleminin üç türü vardır:
  • Kesirli sırt çantası problemi (fractional knapsack problem), objeler parçalara ayrılarak kısmi şekilde çantaya koyulabilir.
  • 0/1 sırt çantası problemi (0/1 knapsack problem), objeler çantaya ya koyulur ya da koyulmaz.
  • Objeler birden fazla kez seçilebilir (unbounded knapsack problem)
Bu alana not ekleyebilirsiniz.
Başka bir sorunuz mu var?
Yorumlar (0)

Henüz yorum yapılmamış.

İlgili Konu
Algoritma Örnekleri
İlgili Kayıtlar
İlginizi Çekebilir