Skip to main content

C++ Fractional Knapsack (Kesirli Sırt Çantası) Problemi Çözümü 🎒

🎯 Bu Rehberde Ne Öğreneceksiniz?​

Bu rehberde, Kesirli Sırt Çantası (Fractional Knapsack) problemini C++ kullanarak çözeceğiz.
Açgözlü (Greedy) algoritma mantığıyla en yüksek değeri sağlayan eşyaları adım adım seçmeyi öğreneceksiniz.
Ayrıca 0/1 Knapsack ile farklarını, oran sıralaması mantığını ve neden bu yöntemin her zaman optimal olduğunu keşfedeceksiniz.

🧠 Teknik Özet​

  • Problem: Sınırlı kapasiteye sahip bir çantada toplam değeri maksimize etmek
  • Yaklaşım: Greedy (Açgözlü)
  • Zaman Karmaşıklığı: O(N log N)
  • Kritik Adım: Eşyaları Değer/Ağırlık oranına göre azalan sırada sıralamak
  • Avantaj: Kesirli (fractional) seçim sayesinde her zaman optimum çözüm

💼 Fractional Knapsack Nedir?​

Bu problemde her eşyanın ağırlığı (weight) ve değeri (value) vardır.
Çantanın kapasitesi W ile sınırlıdır.
Amaç, çanta kapasitesini aşmadan en yüksek toplam değeri elde etmektir.

Fark:

  • 0/1 Knapsack → Eşyayı ya tamamen alırsınız ya hiç almazsınız.
  • Fractional Knapsack → Eşyanın bir kesrini (örneğin %30’unu) alabilirsiniz.

🔍 Açgözlü Algoritma Mantığı​

Açgözlü algoritmalar, her adımda en iyi (yerel maksimum) seçimi yapar.
Bu problemde güvenli seçim (“safe move”), en yüksek değer/ağırlık oranına sahip eşyayı almaktır.

💡 Kanıt:
En verimli (yüksek oranlı) eşyadan başlamak, toplam değeri her zaman maksimum yapar.
Çünkü daha düşük oranlı bir eşyayı önce almak, her durumda daha düşük toplam getirir.

🧩 Adım Adım Fractional Knapsack Çözümü​

  1. Oran Hesapla: Her eşya için değer / ağırlık oranını bul.
  2. Sırala: Eşyaları bu orana göre azalan sırada sırala (O(N log N)).
  3. Çantayı Doldur: Sıralı listedeki eşyaları sırayla al.
    • Eğer eşya sığıyorsa tamamını al.
    • Eğer sığmıyorsa kesrini al, sonra işlemi bitir.
  4. Değeri Güncelle: Alınan her eşyanın değeri kadar toplam değeri artır.
  5. Kapasite 0 olunca dur.

💻 Fractional Knapsack C++ Kodu​

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// Eşyaları değer/ağırlık oranına göre sıralayan karşılaştırıcı
bool compare(pair<float, int> p1, pair<float, int> p2) {
    return p1.first > p2.first;
}

// Ana çözüm fonksiyonu
float fractional_knapsack(vector<int> weights, vector<int> values, int capacity) {
    int len = weights.size();
    float total_value = 0.0;

    // (oran, orijinal_index) çiftleri
    vector<pair<float, int>> ratio(len);
    for (int i = 0; i < len; i++)
        ratio[i] = make_pair((float)values[i] / weights[i], i);

    // Oranlara göre azalan sırayla sıralama
    sort(ratio.begin(), ratio.end(), compare);

    for (int i = 0; i < len; i++) {
        if (capacity == 0) break;

        int idx = ratio[i].second;

        if (weights[idx] <= capacity) {
            capacity -= weights[idx];
            total_value += values[idx];
        } else {
            float fraction = (float)capacity / weights[idx];
            total_value += values[idx] * fraction;
            capacity = 0;
        }
    }
    return total_value;
}

int main() {
    vector<int> weights, values;
    int capacity;

    cout << "Eşya ağırlıklarını girin (-1 sonlandırır): ";
    while (true) {
        int w; cin >> w;
        if (w == -1) break;
        weights.push_back(w);
    }

    cout << "Eşya değerlerini girin (-1 sonlandırır): ";
    while (true) {
        int v; cin >> v;
        if (v == -1) break;
        values.push_back(v);
    }

    cout << "Çanta kapasitesini girin: ";
    cin >> capacity;

    cout << "\nMaksimum elde edilebilir toplam değer: "
         << fractional_knapsack(weights, values, capacity) << endl;
}

🧠 Açıklama: Bu kod, kullanıcıdan veri alır, eşyaları oranlarına göre sıralar ve çanta kapasitesine göre kesirli alım yapar.

📊 Karmaşıklık Tablosu​

ÖzellikAçıklama
YaklaşımAçgözlü (Greedy)
Zaman KarmaşıklığıO(N log N)
Uzay KarmaşıklığıO(N)
AvantajHızlı, optimal sonuç verir
Sınırlama0/1 Knapsack için geçerli değildir

❓ Sıkça Sorulan Sorular (SSS)​

  1. Fractional Knapsack neden her zaman optimal sonuç verir?

Çünkü kesirli alım imkânı, her zaman maksimum verim sağlayan yerel seçimi güvenli hale getirir.

  1. 0/1 Knapsack neden greedy yaklaşım ile çözülemez?

Çünkü 0/1 probleminde kesirli seçim yapılamaz, bu yüzden dinamik programlama gerekir.

  1. Neden değer/ağırlık oranına göre sıralıyoruz?

Bu oran, “en fazla getiriyi en az ağırlıkla sağlama” ölçütüdür.

  1. Oran ve indeks birlikte neden saklanır?

Sıralamadan sonra orijinal eşyanın ağırlık ve değerini bulmak için.

  1. Gerçek dünyada kullanım alanı nedir?

Kaynak tahsisi, bulut sunucu yük dengeleme, yatırım portföyü optimizasyonu gibi durumlar.

🏁 Sonuç​

Bu rehberde, C++ Fractional Knapsack Problemi’ni adım adım çözdük. Greedy algoritmanın O(N log N) karmaşıklığı sayesinde yüksek performanslı sonuçlar elde ettik.

💡 Gerçek dünyada optimizasyonun temeli budur: Her adımda doğru küçük seçimler, büyük kazançlara yol açar.

🚀 Rabisu Bulut platformunda optimizasyon algoritmalarınızı test edin ve en verimli kaynak planlamasını deneyimleyin!