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.

Bir Delinin Hatıra Defteri

Bugün Tuğçe’yle yıllardır kapalı gişe oynayan tek kişilik oyun “Bir Delinin Hatıra Defteri”ne gittik. Giden çoğu kimsenin bildiği gibi kapalı gişe oynamasının sebebi, Behzat Ç. rolü ile ünlenen Erdal Beşikçioğlu’nun oyunu olması. Yaklaşık 1.5 yıldır bilet arıyorduk, kısmet sahte kıyametin olduğu bugüne (21.12.2012) imiş. 🙂 Bilet bulabilmek tabii ki hiç kolay olmadı. Bundan 13 gün önce Berkan’la gecenin bir yarısı (saat 2’ydi) Mithatpaşa Caddesi’ndeki 75. Yıl Sahnesi’nin önündeki gişede beklemeye başladık. İlk iki sırayı kapmayı başarabildiğimiz için de sabah saat 10’da uykusuz, rezil ve biraz da hasta olmaya meyilli ama başarının verdiği hazla birlikte biletlerimizi alıp ordan ayrıldık.

Bir Delinin Hatıra Defteri, aslında Gogol’ün yaklaşık 20 sayfalık bir öyküsü. Bir delinin ya da öykü sürecinde bir yerlerde deliren bir adamın günlüğüne yazdıklarını anlatıyor. Zaten akli dengesi pek yerinde olmayan adamın iyice delirmesi ve toplumdaki yerini sorgulaması genel müdürünün kızına aşık olmasıyla başlıyor. Öykü o kadar güzeldi ki, okurken delinin söylediği kimi aptalca sözlere güldüm, kimi mantık dolu cümlelere ise hayıflandım; bir insanın içinde olduğu sistemi bu şekliyle sorgulayabilmesi sanki delilere mahsustu. Kimilerinden duyduğum “deli aslında hiç de delice konuşmuyor,” yorumlarını da buraya bağladım.

Oyuna giderken içimde, delinin günlüğünü nasıl tiyatrolaştırmış olabileceklerine dair bir merak vardı. Oyun düşündüğüm gibi, delinin kendi günlüğünü okuması üzerine kurgulanmıştı. Biz Akün Sahnesi’ndeki performansını izledik. Sahne ortada, etrafına üç sıra plastik sandalyeler dizilmiş; sahnedeyse vinç benzeri bir iş makinesi var. Ben Erdal Beşikçioğlu sahneye nerden girecek diye düşünürken, oyun başladığı zaman 10 dakikadır orda oturmamıza rağmen delinin vincin üstünde yatar vaziyette oyunun başlamasını beklediğini görmediğimizi fark ettim. Yani oyun daha en başından beklentilerimi karşılamaya başlamıştı. Sahnenin yuvarlak olmasının bir dezavantajı, delinin poposunu bolca izlememiz oldu. Ancak rolü o kadar benimsemişti ki, oyundan oldukça tatmin olarak ayrıldım.

Oyun bundan başka bir dizi tesadüfü de yanında getirdi. Bugünün çokça beklenen o sahte kıyamet günü olmasının yanında oyunun da 300. temsiliydi ve Kemal Kılıçdaroğlu da eşiyle birlikte tam karşımızdaki protokolden oyunu izleyenler arasındaydı. Belki delinin poposunu bu kadar çok görmemizin sebebi de budur, bilemiyorum. 🙂

Technical Service Tracking Automation

– Dev’d

  • for Rüzgar Bilişim
  • on February 2012

– Powered by

  • PHP
  • MySQL
  • CSS
  • CodeIgniter

v1.2.0 Version Notes (updated on: Feb 21, 2012)

– Added to the abilities of Administrator

  • Save and edit forms without sending e-mails
  • Send notification e-mails when the form is edited
  • New attributes are added to the service form
  • Add multiple license numbers

– Fixed

  • Slipped user-interface

v1.1.0 Version Notes (updated on: Feb 15, 2012)

– Added to the abilities of Administrator

  • Edit customer info (including username, password, customer title and -coming from previous version: license no)
  • Edit technical service forms
  • Save edited technical service forms as PDF or HTML
  • Delete customer
  • Delete technical service form

v1.0.0 Version Notes

– Authentication System

  • Administrator of the Technical Service
  • Customers of the Technical Service
  • Both levels of auth system are able to log in with username and password

– Administrators are able to

  • See all the customers
  • Change customers’ information (their unique license code)
  • Add customers
  • Open a technical service form to be billed later for customers
  • See all the technical service forms of customers that were opened before
  • Change his/her own information (including e-mail)
  • Send e-mail to the particular customer that includes technical service form

– Customers are able to

  • See his/her license key
  • See his/her old technical service forms that associated with

– Both user levels are able to

  • Save the technical service form as HTML or PDF document
  • Print the technical service form

Editör v2.0.1

v2.0.1 Version Notes

– Fixed

  • Bug: Operator names were not coming along with prices.
  • Bug: Empty prices were occupying the price slots in price arrays.

Post-Beta Notes

Bugs are fixed. Software is stable in this version.

Editör v2.0.1b

v2.0.1b Version Notes

– Added

  • All prices are splitted with their countries.

Post-Alpha Notes

The software works properly.

%d bloggers like this: