Knapsack (Sırt Çantası) Algoritması

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Sırt Çantası(Knapsack) algoritmasını anlatmaya çalışacağız.

Knapsack (Sırt Çantası) Algoritması nedir ?

Knapsack algoritması mevcut verilerden en optimum verimi alma üzerine kurulu bir algoritmadır.
Şöyle basitçe bir örnek vermek gerekirse bir hırsız düşünün sırt çantasına (knapsack) belirli bir ağırlığa kadar eşya koyabiliyor. Evde ise eşyaların ağırlıkları ve değerleri vardır, hırsız en optimum şekilde kar ile evden ayrılmalı ve çantasını ona göre doldurmalıdır.

Örnek Senaryo

Yukarıda ki tablo da evde bulunan eşyaların ağırlıkları ve beraberinde değerleri bulunmaktadır. Hırsızın sırt çantası ise en fazla 6 Kg‘lık eşya kapasitesi olsun.
Öncelikle her bir eşyanın birim fiyatını hesaplamamız gerekir çünkü eşyaları çantaya birim fiyatı büyük olandan küçük olana doğru bir sırayla koyacağız ki en verimli şekilde işlem tamamlansın.

Fiyatları ağırlıklara bölerek birim fiyatları bulacağız. Birim fiyatlar aşağıdaki gibidir.

Senaryo İşlemleri

Sırt çantamız 6 Kg lık eşya sığdırabileceğimizi söylemiştik ve birim fiyatı büyük olandan başlayıp küçük olana doğru çantaya koyacağımızdan da bahsetmiştik bu örneğimizde sırasıyla 3 > 2 > 4 > 1 eşyaları sırasıyla çantaya koyulacaktır.
3.eşyayı çantaya attığımızı düşünelim. 3 Kg fiyatı 6 ₺ sonrasında 2.eşyayı attığımızda ise toplam ağırlık 5 Kg fiyat ise 9 ₺ oldu. Şimdi bizim çantamızın toplam alacağı ağırlık 6 Kg şuan da çantamızda 1 Kg’lık yer kaldı. Ama ağırlığı 1 Kg olan bir eşya bulunmamakta ve buna ek olarak 4.eşya dan 1 Kg lık alacağımızı düşünerek en optimum performansı yakalamış olacağız çünkü sıra bu şekilde gidiyordu. (3 > 2 > 4 > 1)

Sonuç olarak çantamız 6 Kg ve 10 TL lik eşya almış olduk.

Java Kodu

private static double knapsack(List<Goods> goodsList, double weight){

    double value = 0.0;
    List<Double> list = new ArrayList<>();

    for (Goods goods : goodsList) {
        list.add(goods.getValue() / goods.getWeight());
    }

    double tempWeight = 0.0;
    while (tempWeight < weight){

        double subWeight = weight - tempWeight;

        double maxValue = Collections.max(list);
        int maxIndex = list.indexOf(maxValue);

        if (goodsList.get(maxIndex).getWeight() <= subWeight){
            tempWeight += goodsList.get(maxIndex).getWeight();
            value += goodsList.get(maxIndex).getValue();
        }else{
            double WEIGHT = goodsList.get(maxIndex).getWeight(); // 2
            if (WEIGHT % subWeight == 0){
                double div = WEIGHT / subWeight;
                value += goodsList.get(maxIndex).getWeight() / div;
                tempWeight += subWeight;
            }
        }

        goodsList.remove(maxIndex);
        list.remove(maxIndex);

        if (tempWeight == weight){
            break;
        }
    }
    return value;
}

C++ Kodu

int knapSack(int W, int wt[], int val[], int n){
    int i, w;
    int K[n + 1][W + 1];
 
    for (i = 0; i <= n; i++){
        for (w = 0; w <= W; w++){
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w]
                        = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
 
    return K[n][W];
}

Python Kodu

def KnapsackFrac(v, w, W):
  order = bubblesortByRatio(v, w)            
  weight = 0.0                               
  value = 0.0                               
  knapsack = []                              
  n = len(v)
  index = 0                                  
  while (weight < W) and (index < n):
    if weight + w[order[index]] <= W:        
      knapsack.append((order[index], 1.0))   
      weight = weight + w[order[index]]
      value = value + v[order[index]]
    else:
      fraction = (W - weight) / w[order[index]]  
      knapsack.append((order[index], fraction)) 
      weight = W
      value = value + v[order[index]] * fraction
    index = index + 1
  return (knapsack, value)                       

Proje Kodu : Github

Umarım faydalı olmuştur aklınıza takılan bir yer ya da sormak istediğiniz bir ksıım olursa sormaktan çekinmeyin.
Hoşçakalın.