0/1 Sırt Çantası Problemi Nedir?
0/1 Sırt Çantası Problemi, bilgisayar bilimleri ve optimizasyon alanında sıkça karşılaşılan klasik bir problemdir. Temel olarak, sınırlı bir kapasiteye sahip bir sırt çantasına, her birinin belirli bir ağırlığı ve değeri olan bir dizi öğeden hangilerinin konulacağını belirleyerek toplam değeri en üst düzeye çıkarmayı hedefler.
0/1 Sırt Çantası Problemi, her bir öğenin ya tamamen çantaya konulabildiği (1) ya da hiç konulamadığı (0) kısıtlaması altında, belirli bir ağırlık sınırını aşmadan çantadaki öğelerin toplam değerini maksimize etme problemidir.
Adım adım çözümlü örnekler
Basit bir 0/1 Sırt Çantası Problemi örneği verin.
Diyelim ki sırt çantasının kapasitesi 10 kg. Üç öğe var: Öğe 1: Ağırlık 5 kg, Değer 10$ Öğe 2: Ağırlık 4 kg, Değer 40$ Öğe 3: Ağırlık 6 kg, Değer 30$ Bu durumda, en iyi seçim Öğe 2 (4 kg, 40$) ve Öğe 3 (6 kg, 30$) olur. Toplam ağırlık 10 kg ve toplam değer 70$'dır. Öğe 1 ve Öğe 2'yi almak toplam ağırlığı 9 kg yapar ancak değer 50$'dır. Öğe 1 ve Öğe 3'ü almak toplam ağırlığı 11 kg yapar ve kapasiteyi aşar.
Daha karmaşık bir senaryoda 0/1 Sırt Çantası Problemi nasıl çözülür?
Kapasite 7 kg olan bir sırt çantası için şu öğeler mevcut: Öğe A: Ağırlık 3 kg, Değer 4$ Öğe B: Ağırlık 4 kg, Değer 5$ Öğe C: Ağırlık 5 kg, Değer 7$ Öğe D: Ağırlık 2 kg, Değer 3$ Bu problem dinamik programlama ile çözülebilir. Oluşturulacak bir tablo ile her bir öğe ve kapasite kombinasyonu için maksimum değer hesaplanır. Sonuç olarak, Öğe A (3 kg, 4$) ve Öğe D (2 kg, 3$) seçilirse toplam ağırlık 5 kg ve toplam değer 7$ olur. Öğe B (4 kg, 5$) ve Öğe D (2 kg, 3$) seçilirse toplam ağırlık 6 kg ve toplam değer 8$ olur. Bu, en yüksek değerdir.
Bilgi kartları
Mini test
S1.Aşağıdaki öğelerden hangilerini 5 kg kapasiteli bir çantaya koyarak değeri maksimize edersiniz? Öğe X: Ağırlık 2 kg, Değer 10$ Öğe Y: Ağırlık 3 kg, Değer 15$ Öğe Z: Ağırlık 4 kg, Değer 18$
S2.0/1 Sırt Çantası Problemi hangi kategoriye girer?
S3.Eğer bir öğenin ağırlığı sırt çantasının kapasitesinden fazlaysa ne olur?
Sık yapılan hatalar
Öğeleri değerlerine göre sıralayıp en değerliyi önce çantaya koymak. — Doğrusu: Bu açgözlü bir yaklaşımdır ve her zaman optimal çözümü vermez. Dinamik programlama gibi yöntemler kullanılmalıdır.
Her öğeyi ya tamamen ya da hiç almamak yerine, ağırlığına göre oranlayarak almak. — Doğrusu: Bu, 0/1 Sırt Çantası Problemi'nin temel kuralını ihlal eder. Bu durum fraksiyonel sırt çantası problemine girer.
Sıkça sorulan sorular
0/1 Sırt Çantası Problemi'nin NP-zor olduğu söylenir, bu ne anlama gelir?
NP-zor olması, büyük girdi boyutları için bu problemin verimli (polinom zamanda) bir çözümü olmadığının düşünülmesidir. Pratik uygulamalarda genellikle yaklaşık çözümler veya belirli kısıtlamalar altında çözümler kullanılır.
Dinamik programlama dışında hangi çözüm yöntemleri vardır?
Arama algoritmaları (örn. dal-ve-sınır), sezgisel algoritmalar ve bazen genetik algoritmalar gibi yöntemler de kullanılabilir, ancak dinamik programlama genellikle en yaygın ve garantili optimal çözümü veren yöntemdir.
Bu problem hangi alanlarda uygulanır?
Kaynak planlaması, bütçeleme, ürün seçimi, lojistik, yatırım portföyü oluşturma gibi birçok alanda kullanılabilir.