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.