Sırt çantası problemi
Ağırlık sınırı olan bir yürüyüşçü, çuvalı olan bir hırsız, bütçesi ve proje listesi olan bir şirket: hepsi aynı soruyla karşı karşıyadır. Sınırı aşmadan en fazla değeri elde etmek için neler alınmalı? Bu, sırt çantası problemidir ve ağırlıklar makul büyüklükte tam sayılar olduğunda dinamik programlama onu kesin olarak çözer.
Problem
Her birinin bir ağırlığı ve bir değeri olan n eşya ve en fazla W ağırlık taşıyan bir çanta var. Toplam ağırlığı en fazla W olan ve toplam değeri olabildiğince büyük olan bir eşya kümesi seçin. Her eşya ya bütün olarak çantaya girer ya da dışarıda kalır; 0/1 sırt çantası problemi adı buradan gelir. n eşyayla 2ⁿ olası küme vardır, bu yüzden hepsini denemek kısa sürede imkânsız hâle gelir.
Tablo
best[i][w], yalnızca ilk i eşya kullanılarak w ağırlığına sığabilen en yüksek değer olsun. O zaman best[0][w] = 0 olur ve sonraki her satırda iki seçenek vardır: i. eşyayı dışarıda bırakmak, bu best[i − 1][w] verir; ya da ağırlığı wᵢ sığıyorsa onu koymak, bu da değeri artı best[i − 1][w − wᵢ] verir. Büyük olanı best[i][w] olur. Tabloyu satır satır doldurmak, gereken iki hücrenin her zaman hazır olmasını sağlar.
Bir örnek
Kapasite 7 olsun ve ağırlıkları 1, 3, 4 ve 5, değerleri 1, 4, 5 ve 7 olan dört eşya alın. Yalnızca ilk eşyayla 1 ve üzeri her kapasitenin değeri 1'dir. İkinci eşya eklenince 4 kapasite ikisini birden 5 değerle tutabilir. Üçüncü eşya eklenince 7 kapasite 2. ve 3. eşyaları 9 değerle tutabilir. Ağırlığı 5 ve değeri 7 olan dördüncü eşya, 6 ya da 7 kapasitede 1. eşyayla birlikte 8 verebilir, ama 9 daha iyidir; bu yüzden sağ alt hücre 9'dur: ağırlığı 3 ve 4 olan eşyaları koyun.
Ne kadar zor?
Tablo yaklaşık n·W adım gerektirir. Bu hızlı görünür, ama W bir sayıdır ve d basamaklı bir sayı 10 üzeri d kadar büyük olabilir; yani iş, girdinin uzunluğuyla üstel olarak büyür. Sırt çantası problemi NP-zordur; Richard Karp'ın 1972'deki 21 NP-tam probleminden biriydi. Pratikte tablo, dal ve sınır yöntemi ve iyi yaklaşım şemaları büyük gerçek örnekleri iyi çözer.
Tarihçe ve kullanım alanları
Ad, 20. yüzyılın başlarında matematikçi Tobias Dantzig'e dayanır; oğlu George Dantzig de 1957'de problem için klasik bir açgözlü yöntem verdi. Sırt çantası problemleri bütçelemede ve portföy seçiminde, ham maddeyi olabildiğince az fireyle kesmede, yük yüklemede ve hatta erken açık anahtarlı kriptografide karşımıza çıkar: 1978 tarihli Merkle–Hellman kriptosistemi bir sırt çantası problemi üzerine kurulmuştu ve birkaç yıl sonra kırıldı.
Kendiniz keşfedin
Uygulamayı açın, Tablo görünümüne geçin ve Adım'a basın. Turuncu hücre doldurulan hücredir; mavi hücreler ise karşılaştırdığı iki hücredir: hemen üstteki hücre ve üst satırda, eşyanın ağırlığı kadar soldaki hücre. Son hücreden sonra geriye okuma sağ alt köşeden turuncuyla yukarı tırmanır ve konulan eşyalar tablonun altında görünür.
Sık sorulan sorular
0/1, sınırlı ve sınırsız sırt çantası arasındaki fark nedir?
0/1 sürümünde her eşya en fazla bir kez alınır. Sınırlı sürümde her eşyadan sınırlı sayıda kopya vardır, sınırsız sürümde ise istenen sayıda. Tablo bunlar arasında yalnızca biraz değişir.
Açgözlü yöntem sırt çantası için hiç doğru sonuç verir mi?
Eşyaların bölünebildiği kesirli sırt çantası probleminde önce ağırlık başına değeri en yüksek olanı almak en iyi sonucu verir. Bütün eşyalarda ise sonuç çok uzak olabilir; yine de açgözlü yöntemin sonucu ile tek başına en değerli eşyadan iyi olanı her zaman en iyi değerin en az yarısıdır.
Tablo ne kadar bellek gerektirir?
Tam tablo için (n + 1)·(W + 1) hücre; eşyaları geriye doğru okumak için gereken de budur. Yalnızca en iyi değer isteniyorsa, sağdan sola doldurulan W + 1 hücrelik tek bir satır yeterlidir.
Sırt çantası, alt küme toplamıyla aynı şey mi?
Alt küme toplamı, her eşyanın değerinin ağırlığına eşit olduğu ve sorunun çantanın tam olarak doldurulup doldurulamayacağı olduğu özel durumdur. O da NP-tamdır ve aynı türden bir tabloyla çözülür.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Sırt çantası problemini deneyin