- Dolduruluyor
- Okunan
- Cevap
Sırt çantası problemi
Ancak belli bir ağırlığı taşıyabiliyorsunuz ve her eşyanın bir ağırlığı ve bir değeri var. En fazla değeri taşımak için hangi eşyaları almalısınız? Her kombinasyonu denemek, her yeni eşyayla işi iki katına çıkarır. Eşya satırları ve kapasite sütunlarından oluşan bir tablo ise en iyi çantayı hücre hücre bulur. Bir eşyayı çantaya koymak için ona dokunun; çıkarmak için ona (çantadayken ya da raftayken) yeniden dokunun. Çanta ağırlığa göre dolar ve kutucuklar, koyduğunuz doları mümkün olan en iyi değerle karşılaştırır. En iyi çantayı görmek için En iyi yerleşim'e basın. Panelde eşyaların kilogramlarını ve dolarlarını değiştirin, eşya ekleyin ya da kaldırın ve çanta kapasitesini ayarlayın. Tablo görünümü, dinamik programlamanın en iyi çantayı nasıl bulduğunu gösterir: tablonun dolmasını izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım'ı ve Geri'yi kullanın; herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Her satır bir eşya ekler, her sütun kilogram cinsinden bir kapasitedir ve her hücre sığabilecek en çok doları tutar. Tablo seçiliyken ok tuşları adım adım ilerletir, boşluk tuşu oynatır ve duraklatır, Home ve End tuşları başa ve sona atlar.
Nasıl çalışır
- Kutulara dokunarak onları çantaya koyun ve çantanın kilogram cinsinden ağırlıkla dolduğunu izleyin.
- Dolar cinsinden mümkün olan en iyi değere ulaşmaya çalışın ya da en iyi çantayı görmek için En iyi yerleşim düğmesine basın.
- Tablo görünümünü açın ve her hücrenin bir eşyayı koymakla bırakmak arasında nasıl seçim yaptığını izlemek için Oynat'a basın.
Tablo nasıl çalışır?
Her satır bir eşya ekler ve her sütun 0'dan çantanın kapasitesine kadar bir kapasitedir. Bir hücre, kendi satırına kadarki eşyaları kullanarak o kapasiteye sığabilen en yüksek değeri tutar. Yeni eşya olmadan bu, üstteki hücredir. Yeni eşyayla, eğer sığıyorsa, eşyanın değeri artı kalan ağırlık için en iyi değerdir; bu değer üst satırda, eşyanın ağırlığı kadar soldadır. Hücre ikisinden büyük olanı tutar. Hiç eşya olmayan ilk satır tamamen sıfırdır.
Eşyaları geriye doğru okumak
Sağ alt hücre en iyi değerdir. Eşyaları bulmak için oradan başlayın ve onu üstteki hücreyle karşılaştırın: aynıysa son eşyaya gerek yoktu; daha büyükse eşya çantadadır, bu yüzden ağırlığını çıkarın ve o sütuna geçin. İlk satıra varana kadar her seferinde bir satır yukarı çıkın. Uygulama bu geriye okumayı turuncuyla gösterir ve konulan eşyaları tablonun altında listeler.
Sık sorulan sorular
0/1 sırt çantası problemindeki 0/1 ne anlama gelir?
Her eşya bir kez konulur ya da hiç konulmaz; asla bir kısmı konulmaz ve asla iki kez konulmaz. Eşyalar pirinç taneleri gibi bölünebilseydi, önce ağırlık başına değeri en yüksek olanları koymak en iyi sonucu verirdi; buna kesirli sırt çantası problemi denir.
Neden önce ağırlık başına değeri en yüksek eşya konulmuyor?
Çünkü bütün eşyalar boşluk bırakabilir. Kapasite 7 iken ağırlıkları 1, 3, 4 ve 5, değerleri 1, 4, 5 ve 7 olan eşyalarda ağırlık başına değeri en yüksek olan, ağırlığı 5 olan eşyadır; o da yalnızca ağırlığı 1 olan eşyaya yer bırakır ve toplam 8 olur. Ağırlığı 3 ve 4 olan eşyalar ise birlikte 9 değerindedir.
Sırt çantası algoritması ne kadar hızlı?
Tabloda (eşya sayısı + 1) çarpı (kapasite + 1) hücre vardır ve her biri bir adımda doldurulur. Bu, küçük kapasiteler için hızlıdır, ama kapasite çok büyük bir sayı olabilir; bu yüzden problem genel olarak NP-zordur ve tablo yöntemine sözde polinom denir.
Aynı eşya iki kez konulabilir mi?
Burada konulamaz. Sınırsız sırt çantası probleminde her eşya istenildiği kadar alınabilir; bu durumda tablo, para üstü uygulamasında olduğu gibi, üst satır yerine aynı satırda soldaki hücreyi okur.
Herhangi bir veri bir yere gönderiliyor mu?
Hayır. Her şey tarayıcınızda hesaplanır ve son ayarlarınız bu tarayıcının yerel depolamasında kalı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.
Editöre Git