Dinamik Programlama İle Knapsack (1/0)

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Dinamik Programlama ile Knapsack (1/0) Algoritmasını anlatmaya çalışacağız.

Knapsack (1/0) Nedir?

Sırt çantası olarak Türkçe’ye geçen Knapsack kelimesi bilgisayarda bir çözüm yönteminin adıdır. Son yazımızı okuyan arkadaşlar problemin ne olduğunu az çok biliyordur.

Knapsack (1/0) Problemi Nedir?

Bir hırsız, hırsızlık yapmak için bir eve giriyor ve elinde belli bir miktar kapasitesi olan bir sırt çantası var. Evde çeşitli değerli nesneler var. Bize bu nesnelerin piyasa değeri ve çantamızda kaplayacağı yer veriliyor. Amacımız da hırsızın en karlı hırsızlığını yapmasını sağlamak. Sınırlamamız sırt çantasının kapasitesini açmamak. Ancak son yazımızdan farklı olarak bu sefer bir objeyi ya alıyoruz ya da almıyoruz. Yani yarısını veya çeyreğini çalamıyoruz. Ancak tamamını çalabiliyoruz. Alıp almama yani bilgisayarda true/false dediğimiz olayı göstermek için (1/0) kavramını kullanıyoruz.

Çözüm Hakkında

Akla ilk gelen çözüm, recursive bir fonksiyon yazarak her obje için bunu alsam ne olur almasam ne olur diye hesaplamak. Bu da her obje için (1/0) 2 durum deneyeceğimiz için 2^n maliyet oluyor. Bu da ancak 20 objeye kadar hesaplamamıza olanak sağlıyordu ki bu da çok kötü bir performans. Biz şimdi Dinamik Programlama yöntemini kullanarak 20000 objeye kadar hesaplayabileceğiz.

Çözüm

Func hesapla(objeNo , kalanYer){

if(dp[objeNo][kalanYer] != -1) return;

durum1 = hesapla(objeNo + 1 , kalanYer - yer[objeNo]) + deger[objeNo]

durum2 = hesapla(objeNo + 1 , kalanYer);

dp[objeNo][kalanYer] = max(deger1 , deger2);

}

Şimdi yukarıda yazdığım kaba kodu biraz inceleyelim. Üstteki if kontrolü en önemli nokta. Bu satır eğer bir dp değeri hesaplandıysa tekrar hesaplamayı engelliyor. Böylelikle her dp değeri yalnızca 1 kere hesaplanmış oluyor. İki farklı durum var ben bu objeyi ya alırım ya almam. Bu iki durumu durum1 ve durum2 değişkenlerinde hesaplıyoruz. durum1 değişkeni bize eğer objeNo’da bulunan objeyi alırsam olabilecek en verimli hırsızlığın değerini tutuyor. durum2 ise şu anda bulunan objeyi almazsam olabilecek en iyi sonucu tutuyor. dp[i][j] ise i. objeye kadar j yer bırakarak yapılabilecek en verimli hırsızlığı tutuyor.

Biraz ağır gelmiş olabilir kodu iyice hazmederek tekrar tekrar okumanızı tavsiye ederim. Dp dizimizin de ne işe yaradığını söylediğimize göre cevabımız dp dizisinde saklı. Bütün objelere bakmamız en mantıklısı olduğu için dp[N] boyutundaki bütün değerlere bakarak en büyüğünü hesaplamalıyız. Bu en büyük değer bizim en verimli hırsızlığımız olacaktır.

Maliyet Hesaplaması

dp dizisinin ilk boyutu obje sayısı kadar olacaktır yani N. İkinci boyutu da kalan yeri tuttuğu için bizim çantamızın kapasitesi olacaktır buna da M diyelim. Her dp değeri bir kere hesaplanacağı için maliyetimiz en kötü durumda N*M olacaktır. Yani O(N^2) diyebiliriz böylelikle N değeri 20000’e kadar hesaplayabilecektir.

Şimdi gerçek kodları paylaşarak yazımızı bitirelim.

#include<stdio.h>
 
#define N 128
 
int CostTable[N][N];
int Weight[N];
int Benefit[N];
 
int total_weight = 10;
int item_count = 6;
 
inline int max(int a, int b){
    return a > b ? a : b;
}
 
int RecursiveKnapsack(int i, int w){
    if(CostTable[i][w] != -1)
        return CostTable[i][w];
 
    if(Weight[i] > w)
        CostTable[i][w] = RecursiveKnapsack(i - 1, w);
    else
        CostTable[i][w] = max(RecursiveKnapsack(i - 1, w), RecursiveKnapsack(i - 1, w - Weight[i]) + Benefit[i]);
}
 
int main(){
 
    Weight[1] = 6;
    Weight[2] = 1;
    Weight[3] = 2;
    Weight[4] = 5;
    Weight[5] = 4;
    Weight[6] = 3;
 
    Benefit[1] = 10;
    Benefit[2] = 5;
    Benefit[3] = 7;
    Benefit[4] = 12;
    Benefit[5] = 8;
    Benefit[6] = 6;
 
    /*
     * Set all values of 2D matrix CostTable to Minus 1
     */
    for(int i = 0; i <= item_count; ++i)
        for(int w = 0; w <= total_weight; ++w)
            CostTable[i][w] = -1;
 
    printf("Max Benefit: %d\n", RecursiveKnapsack(item_count, total_weight));
 
    return 0;
}

Okuduğunuz için teşekkür ederim umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.

Tüm Algoritma Derslerimiz İçin tıklayınız.