binary-search

Knapsack (Sırt Çantası) Algoritması

Java Kotlin Eğitimi

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Sırt Çantası(Knapsack) algoritmasını anlatmaya çalışacağız.

Knapsack (Sırt Çantası) Algoritması nedir ?

Knapsack algoritması mevcut verilerden en optimum verimi alma üzerine kurulu bir algoritmadır.
Şöyle basitçe bir örnek vermek gerekirse bir hırsız düşünün sırt çantasına (knapsack) belirli bir ağırlığa kadar eşya koyabiliyor. Evde ise eşyaların ağırlıkları ve değerleri vardır, hırsız en optimum şekilde kar ile evden ayrılmalı ve çantasını ona göre doldurmalıdır.

Örnek Senaryo

Eşya Ağırlık Fiyat
14 Kg2 ₺
22 Kg3 ₺
33 Kg6 ₺
42 Kg2 ₺

Yukarıda ki tablo da evde bulunan eşyaların ağırlıkları ve beraberinde değerleri bulunmaktadır. Hırsızın sırt çantası ise en fazla 6 Kg‘lık eşya kapasitesi olsun.
Öncelikle her bir eşyanın birim fiyatını hesaplamamız gerekir çünkü eşyaları çantaya birim fiyatı büyük olandan küçük olana doğru bir sırayla koyacağız ki en verimli şekilde işlem tamamlansın.

Fiyatları ağırlıklara bölerek birim fiyatları bulacağız. Birim fiyatlar aşağıdaki gibidir.

Eşya Ağırlık Değer Birim Fiyat
14 Kg2 ₺0,5 ₺
22 Kg3 ₺1,5 ₺
33 Kg6 ₺2,0 ₺
42 Kg2 ₺1,0 ₺

Senaryo İşlemleri

Sırt çantamız 6 Kg lık eşya sığdırabileceğimizi söylemiştik ve birim fiyatı büyük olandan başlayıp küçük olana doğru çantaya koyacağımızdan da bahsetmiştik bu örneğimizde sırasıyla 3 > 2 > 4 > 1 eşyaları sırasıyla çantaya koyulacaktır.
3.eşyayı çantaya attığımızı düşünelim. 3 Kg fiyatı 6 ₺ sonrasında 2.eşyayı attığımızda ise toplam ağırlık 5 Kg fiyat ise 9 ₺ oldu. Şimdi bizim çantamızın toplam alacağı ağırlık 6 Kg şuan da çantamızda 1 Kg’lık yer kaldı. Ama ağırlığı 1 Kg olan bir eşya bulunmamakta ve buna ek olarak 4.eşya dan 1 Kg lık alacağımızı düşünerek en optimum performansı yakalamış olacağız çünkü sıra bu şekilde gidiyordu. (3 > 2 > 4 > 1)

Sonuç olarak çantamız 6 Kg ve 10 TL lik eşya almış olduk.

Java Kodu

C++ Kodu

Python Kodu

Proje Kodu : Github

Umarım faydalı olmuştur aklınıza takılan bir yer ya da sormak istediğiniz bir ksıım olursa sormaktan çekinmeyin.
Hoşçakalın.

Yusuf Çakal

Cumhuriyet Üniversitesi - Bilgisayar Mühendisliği (2014-2018)

Yorum Yaz

Haftalık Bülten

Mobilhanem'de yayınlanan dersleri haftalık mail almak ister misiniz?