Kesirli Sırt Çantası

Açgözlü Algoritmalar O(n log n) O(1)

Öğeler bölünebildiğinde ağırlık sınırı altında değeri en büyükler: öğeleri değer/ağırlık sırasıyla al, sonuncuyu kesirli böl.

w10 · v606.0/kg—

w20 · v1005.0/kg—

w30 · v1204.0/kg—

Çanta0/50

kapasite 50toplam0

1/13

Eşyalar değer/ağırlık oranına göre sıralandı — kilo başına en değerli önce.

DeğişmezÇanta, ağırlık birimi başına en iyi değeri tutar; burada açgözlülüğü optimal yapan, bir eşyayı bölebilmektir.

değerlendiriliyortamamı alındıkesri alındı

fractional-knapsack.c

/* items sorted by value/weight ratio (desc) */
double fracKnapsack(int w[], int v[], int n, int W) {
    double total = 0;
    int remaining = W;
    for (int i = 0; i < n && remaining > 0; i++) {
        if (w[i] <= remaining) {
            remaining -= w[i];       /* take it all */
            total += v[i];
        } else {
            double frac = (double)remaining / w[i];
            total += v[i] * frac;    /* take a fraction */
            remaining = 0;
        }
    }
    return total;
}

Kesirli Sırt Çantası nasıl çalışır?

Önce kilogram başına en değerli. Sığdıkça öğeleri bütün al, sonra çantayı bir sonrakinin kesriyle doldur — açgözlü seçimi kanıtlanabilir optimal yapan bölünebilirliktir.

Ne zaman kullanılır?

Bölünebilir kaynaklar: sıvılar, bütçeler, bant genişliği. (Bölünemez öğeler 0/1 sırt çantası DP ister.)