Fractional Knapsack Problem

Algoritma dersi alırken bir hafta Knapsack Problem ile ilgili küçük bir araştırma yapmıştım. Türkçe kaynak pek yoktu, İngilizce olaraksa basit bir dil kullanan çok az sayıda yayın buldum. Bunlardan birini de University of Nebraska-Lincoln’ün Computer Science dekanı Dr. Steve Goddard’ın dersi için hazırladığı sunumlardan birinde buldum. Oldukça basit bir şekilde 0/1 Knapsack Problem’ı açıklamış. Üstüne biraz daha araştırma yaparak Knapsack Problem üzerine çalıştım ve algoritma anlatımını daha da basitleştirdim. Sonra da hem Türkçe bir kaynak bulunması için, hem de kendime ilerde referans olarak bırakmak için buraya yazmaya karar verdim. 🙂

Knapsack Problem’ın iki çeşidi var. İlki, Dynamic Programming ile çözülen 0/1 Knapsack Problem. İkincisi de Greedy Algorithm ile çözülen Fractional Knapsack Problem. Fractional Knapsack Problem çok daha kolay. O nedenle öncelikle Fractional’ın üstünden geçeceğim, sonra da 0/1’ı daha detaylı bir şekilde anlatacağım. Ama öncelikle bilmeyenler için Knapsack Problem’ın biraz üstünden geçelim. Bu problemde elimizde sınırlı hacme sahip boş bir çanta var. Bu çantaya, elimizdeki çeşitli hacimdeki ve değerdeki eşyaları sığdırmaya ve bu yerleştirmeden maksimum değer elde etmeye çalışıyoruz. Yani amacımız çantamızı doldurarak maksimum değeri elde etmek. Değişkenlerimiz: Çantanın toplam hacmi (W), eşyalarımızın hacimleri (w_i) ve eşyalarımızın değerleri (b_i). Burdaki “i”yi, eşyalarımızın bir nevi id’si olarak düşüneceğiz. Yani 2 numaralı eşyamızın hacmi w_2, değeri de b_2 değişkeniyle anılacak. Devam edecek olursak…

Fractional Knapsack Problem, eşyaları bölerek kullanmamıza izin verir. Yani hacmi 6 olan bir eşyayı çantaya tüm olarak koymak zorunda değiliz. 2/3’ünü alıp çantaya koyma imkanımız var. Peki bunun bize ne gibi bir faydası olabilir? Diyelim ki çantamızı son eşyaya kadar doldurduk ve çantamızda 4 hacimlik yer kaldı. Kullanabileceğimiz son eşyamızın da hacmi 6. Yani eşyayı olduğu gibi yerleştiremiyoruz. Biz de eşyanın 2/3’ünü alıp çantaya koyuyoruz. Böylece eşyanın değerinin 2/3’ünü de çantamızın getireceği değere ekleyebiliyoruz. Çok basit.

Şimdi küçük bir örnek yapalım. Aşağıda her birinin hacim ve değerleri verilen 4 eşyamız var. Çantamızın hacmi de, W = 6.

Hacim (weight); Değer (benefit)

w_1 = 3; b_1 = 5
w_2 = 2; b_2 = 3
w_3 = 1; b_3 = 0.5
w_4 = 2; b_4 = 2

Açıkça görüldüğü üzere üç eşyanın toplam hacmi 8, yani çantaya hepsini koyamıyoruz. Yapacağımız ilk işlem, her bir eşyanın göreceli değerlemesini bulmak. Bunun için hacim başına düşen değeri bulacağız. Biz buna kazanç (n_i) diyelim.

n_1 = b_1 / w_1 = 5/3
n_2 = b_2 / w_2 = 3/2
n_3 = b_3 / w_3 = 0.5/1 = 1/2
n_4 = b_4 / w_4 = 2/2

Görüldüğü üzere n_1 > n_2 > n_4 > n_3. Bu sıralama, bizim eşyaları çantaya koyma sıralamamız. Çantada yer oldukça koymaya çalışacağımız eşya önce 1 numara, sonra yer kalırsa 2 numara, sonra yine yer kalırsa 4 numara, sonra yine yer kalırsa 3 numara.

1 numaralı eşyayı çantaya koyduk. Çantanın kalan hacmi: 3. Elde ettiğimiz toplam değer: 5.
2 numaralı eşyayı çantaya koyduk. Çantanın kalan hacmi: 1. Elde ettiğimiz toplam değer: 8.
4 numaralı eşyayı çantaya koyamadık. Çünkü çantanın kalan hacmi 1, sıradaki eşyanın (4 numara) hacmi 2. Burda dikkat etmemiz gereken şey, 3 numaralı eşyanın hacmi 1 olmasına rağmen bu eşyayı değil, hacmi 2 olan 4 numaralı eşyayı koymak istiyoruz. Çünkü 4 numaralı eşyanın 1 hacminden kazanacağımız değer daha fazla. Çantanın kalan hacmi 1 ise, biz de 4 numaralı eşyanın 1 hacmini alıp çantaya koyuyoruz. Bu hacim bize 1 değer getirecek.

Çantanın kalan hacmi: 0. Elde ettiğimiz toplam değer: 9.

Böylece çantamızı optimal şekilde doldurmuş olduk. Çantaya koyduğumuz eşyalar 1 ve 2’nin tamamı ile 4’ün bir kısmı. Elde ettiğimiz toplam değer ise 9 oldu. Bu çözüm için pseudo-code vermiyorum, çünkü oldukça basit.

Aslında 0/1 Knapsack Problem’ı da bu postta anlatacaktım ama yazacak pek gücüm kalmadı. Önümüzdeki günlerde 0/1 yazısı da gelecek.

Dipnot 1: Aslında weight’in türkçesi “ağırlık” anlamına geliyor ama ben hacim demeyi tercih ediyorum.

Dipnot 2: Dr. Steve Goddard’ın orijinal sunumuna ulaşmak için buraya tıklayabilirsiniz.

3 thoughts on “Fractional Knapsack Problem

Leave a Reply