Kesirli Sırt Çantası

#Nasıl çalışır?

Kesirli sırt çantası, 0/1 sırt çantasının eşyaların bölünebildiği hâlidir: bir eşyanın tamamını değil, istediğimiz kadarını alabiliriz (toz altın, baharat, kumaş gibi).

Bu durumda açgözlü yaklaşım en iyi çözümü verir: eşyaları birim ağırlık başına değere (v / w) göre sırala, en değerliden başlayarak tamamını al; sığmayan ilk eşyadan kalan yer kadar kes ve dur.

Aynı eşyalarla 0/1 sırt çantasında kapasite 7 için en iyi değer 9'dur; kesirli hâlde 9,67'ye çıkar. 0/1 hâlinde aynı açgözlü kural yanılabilir, çünkü eşya bölünemediği için boşta kalan yer değerlendirilemez. Bu yüzden 0/1 sırt çantası DP ister.

#Kendin dene

#Adım adım

1. 01Her eşya için v / w oranını hesapla.
2. 02Eşyaları bu orana göre büyükten küçüğe sırala.
3. 03Sığan eşyaların tamamını al.
4. 04Sığmayan ilk eşyadan kalan kapasite kadar kesir al ve dur.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

# (weight, value) of each item; any fraction of an item may be taken.
ITEMS = [(1, 1), (3, 4), (4, 5), (5, 7)]


def fractional_knapsack(items: list, capacity: float) -> float:
    total = 0.0
    for w, v in sorted(items, key=lambda it: it[1] / it[0], reverse=True):  # best value per weight first
        if capacity <= 0:
            break
        take = min(w, capacity)  # the whole item, or the part that still fits
        total += v * take / w
        capacity -= take
    return total


print(f"{fractional_knapsack(ITEMS, 7):.2f}")  # 0/1 knapsack only reaches 9

#Karmaşıklık

Sıralama baskındır. Seçim (selection) algoritmasıyla kesilecek eşyayı bulmak O(n)'e de indirilebilir. Sonuç her zaman en iyidir: daha düşük oranlı bir eşyadan bir birim almak, daha yüksek oranlı bir eşyadan bir birim almaktan asla iyi olamaz.

#Ne zaman kullanılır?

Bölünebilir kaynakların paylaştırılması: bütçe dağıtımı, yük ve yakıt planlaması, yatırım miktarlarının kesirli seçimi. Ayrıca 0/1 sırt çantası için dal-sınır (branch and bound) yöntemlerinde üst sınır hesaplamak için kullanılır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.