Binary Knapsnak Problem - Dynamic Programming

Nedir Sırt Çantası Problemi: Kısıtlı kapasitesi olan sırt çantan var . Boyutları ve değerleri olan parçalanamayan eşyalar var. Çantaya alabileceği kadarını koyduk , değer maksimum kaç olur?

Problemin alt parçasına inelim. W kapasiteli bir çantanın maksimum değeri V.
X eşyası eklendiyse onu çıkardığımız  zaman W- Sx kapasiteli çantada maksimum değeri elde ederiz.
Sx: X eşyasının boyutu
Vx: X eşyasının değeri

Value = max{ Value(W-Sx)+Vx , Value(W) }
Value(0) = 0;

Bir örnek üzerinden gidelim:
1. obje boyutu=4 değeri =10
2. obje boyutu=2 değeri =8
3. obje boyutu=3 değeri =3
Çantanın boyutu=5

 Öncelikle 1 tabloya ihtiyacımız var

 Tablonun boyutu: Çantanın kapasitesi kadar sütun(bizim örneğimizde 5) , obje sayısı kadar satır.
[i,j] hücresi j kapasiteli bir çanta ve ilk i obje varken elde ettiğimiz maksimum kazanç.

Birinci satırı doldurmaya başlıyoruz. 1. objenin boyutu 4 ,değeri 10 . Çantanın kapasitesi 4 olana kadar 1. objeyi ekleyemiyoruz bu yüzden 4e kadar kazancımız hep 0. 4e geldik 1. objeyi ekleyebilirim. 1. objeyi eklediğimizde kazancımız 10 oldu. 5e geldik ekleyeceğimiz başka obje yok yine 1. objeyi ekliyoruz.

2. objede geldik boyutu=2 değeri=8
Kapasite 1 : 2. obje sığmıyor , kazanç 0. Üst satıra bakıyoruz oradaki değer de 0. 0 yazıyoruz.

Kapasite 2:  Obje sığıyor , kazanç=8 , bir üst satıra bakıyoruz kazanç 0 imiş. Eklediğimizde değer artıyor o sebepten ekliyoruz.Hücrenin değeri 8 oluyor.

Kapasite 3: Objenin boyutu 2 , 1 birim yer kaldı , 1 birimlik yerde önceki objelerle neler yapabiliriz? Bir üst satırda 1.sütuna bakıyoruz değeri 0. Toplam kazanç 8+0=8. Bir üst satıra bakıyoruz değeri 0. 8>0 olduğu için objeyi ekliyoruz, kazanç 8 oluyor.

Kapasite 4: Burada iş biraz değişiyor. Objeyi ekleyelim kazanç 8 , 2 birim yer kalıyor . Üst satırdan 2 birim yerin değerine bakıyoruz 0, 8+0 toplam kazanç 8. Üst satırın 4. sütununa bakıyoruz. Peki ne için , önceki objelerle 4 kapasitesinde bir çanta için maksimum ne kadar kazanç elde etmişiz : 10 . 10 > 8 olduğu için 2. objeyi bu sefer eklemek yerine üstteki kazançla devam ediyoruz. Hücrenin değeri 10 oluyor.

Kapasite 5: 2. objeyi koyarsak 3 birim yer kalıyor. Üst satırdan bakıyoruz değeri 0 toplam kazanç 8 oluyor . Üst satırdan 5. sütuna baktık değer 10 daha büyük , 2. objeyi koymuyoruz.

 Buraya kadar genel mantık şu şeklide ilerliyor:

i. obje için
o anki kapasite = K
objenin boyutu = H
objenin değeri=P

K<H
Objeyi ekleyemiyoruz. Value[i][K]=Value[i-1][K],  Value[0][K]=0

K=H
Eklediğimizde elde ettiğimiz kazanç , eski kazançtan daha büyükse objeyi ekliyoruz.
 if (P > Value[i-1][K] )
    Value[i][K]=P
else
   Value[i][K]=Value[i-1][K]

K>H
Bu durumda kalan birimin değerini de eklememiz lazım.Eğer objeyi eklediğimizde elde ettiğimiz değer + kalan birimden gelen değer , önceki değerden büyükse objeyi ekliyoruz.

if (P + Value[i-1][K-H] > Value[i-1][K])
    Value[i][K]=P + Value[i-1][K-H]
else
   Value[i][K]=Value[i-1][K]


Tablonun son hali

Bu 3 objeyle 5 birim kapasiteli bir çantada maksimum bu kazanç elde ediyoruz: Value[2][4] = 11

11 i neleri çantaya ekleyerek elde ettik?
5 birimlik çantada 1 ve 2 objelerle max kazanç (Value[1][4]): 10
5 birimlik çantada 1 2 3 objelerlerle max kazanç (Value[2][4]): 11
3. objeyi eklemişiz ki kazanç değişmiş.

3 objeyi eklemeye nasıl karar veriyorduk:
Boyutu 3 olduğu için 2 birim yer kalıyor , bir üst satırdan 2 birim yerden maksimum ne kadar kazanç elde ettiğimize bakıyoruz : 8 , 8 i nasıl elde ettik aynı sütunun üst satırına bakıyoruz kazanç 0 imiş 2. objeyide hesaba katınca kazanç 8 olmuş ; demekki 2. objeyide eklemişiz. 2. objenin boyutu 2 , başka yerimiz kalmadı.
Demekki 2. ve 3. objeleri eklemişiz.

Two Egg Problem - İki Yumurta Problemi

Önce problemin tanımını yapalım:

n katlı bir binadayız , iki adet yumurtamız var . Yumurtalar x. katın altındaki katlardan atınca kırılmıyor, x ve üzeri katlardan atılınca kırılıyor. Kırılmadığı sürece yumurtayı tekrar tekrar kullanabilirsiniz. Minimum kaç atışta yumurtanın kırılmaya başladığı katı bulursunuz?

Akla gelen ilk çözümler:

• 1. kattan başlarız ilk nerede kırıldıysa x odur.

 En iyi Durum: İlk katta kırıldıysa tek atışla bulduk.
 En kötü Durum: En üst katta kırılıyorsa n -1 atışta bulduk.

•  İlk yumurtayı orta kattan atarız.

kırıldıysa : 2. yumurtayı ilk kattan atmaya başlarız, taki kırılana kadar
kırılmadıysa : n/2 ile n. katlar arasında kırılıyor. Bu katların ortasından atış yapıyoruz( 3* n / 4). Böyle devam ediyoruz.(Binary search mantığı).
En kötü Durum: yumurtanın n/2-1 katta kırılması. (Benim de aklıma gelen çözüm bu olmuştu)

Gelelim ideal çözüme bunu direk bir örnekle açıklayacağım. Diyelim ki binamız 100 katlı iddiamız 14 atışta ben nerede kırıldığını bulurum. Nasıl mı?

14. kattan atalım. İlk atış hakkımı kullandım. Kaldı 13.

Kırıldı: 1 den 13 e kadar tek tek deniyoruz.

Kırılmadı: İlk 14 katta kırılmıyor. 1 atış yaptık , 13 atış hakkımız kaldı . 14 + 13 = 27 .

27. kattan atalım. Kaldı 12.

Kırıldı: 15 ten 26. kata tek tek deniyoruz.

Kırılmadı: İlk 27 katta kırılmıyor. 2 atış yaptık , 12 hakkımız kaldı. 27+12=39.(14+13+12)

39. kattan atalım: Kaldı 11

Kırıldı: 28 den 38. kata tek tek deniyoruz.

Kırılmadı: İlk 39 katta kırılmıyor. 39+11=50.(14+13+12+11)

.
.
.

(14+13+12+11+...+4 = 99)39. kattan atalım: Kaldı 3
Kırıldı : (14+13+12+11+...+5+1 = 96)96. kattan 98. kata tek tek deniyoruz.
Kırılmadı: İlk 99 katta kırılmıyor. 100. kattan atıyoruz. Kırılacaktır.

n katlı bina için q atış garantiler ise

q+(q-1)+(q-2)+.....1 =  q*(q+1)/2 >= n olması gerekir.

Güzel çözüm değil mi ? Tabi bu problemde yumurta sayısı da değiştirilebilir, strateji aynı.