Knapsack problemi
- Algoritmalar kursu
- İleri seviye
- Ders 13/56
- 4 dk
Ağırlık ve değer verilen eşyalarla kapasiteyi doldurma problemini öğrenirsin.
Knapsack problemi
Knapsack (sırt çantası): ağırlık ve değeri verilen eşyalarla, kapasiteyi aşmadan en yüksek değeri doldur.
0/1 knapsack: her eşya ya alınır ya alınmaz; parçalama yoktur.
Knapsack, kaynak tahsisi ve yatırım kararlarında kullanılır; klasik DP problemidir.
0/1 vs fractional
0/1 knapsack'te eşya ya alınır ya alınmaz. Fractional knapsack'te ise eşya parçalanabilir; greedy optimim verir.
0/1 knapsack için dinamik programlama gerekir; greedy her zaman optimim vermez.
Bu ayrım, hangi yöntemin uygulanacağını belirler; önemli bir karardır.
Uygulama Knapsack brute
knap_brute(W, weights, values, n) yaz. Recursive brute-force 0/1 knapsack. print(knap_brute(50, [10, 20, 30], [60, 100, 120], 3)) ile 220 yazdır.
Başlangıç kodu
def knap_brute(W, weights, values, n):
# Knapsack bruteÖrnek çözüm
def knap_brute(W, weights, values, n):
# Knapsack brute
if n == 0 or W == 0:
return 0
if weights[n - 1] > W:
return knap_brute(W, weights, values, n - 1)
take = values[n - 1] + knap_brute(W - weights[n - 1], weights, values, n - 1)
skip = knap_brute(W, weights, values, n - 1)
return max(take, skip)
print(knap_brute(50, [10, 20, 30], [60, 100, 120], 3))Beklenen çıktı
220
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 0/1 knapsack'te her eşya nasıl ele alınır?
- Yarı alınır
- Parçalanır
- Bölünür
- Ya alınır ya alınmaz Doğru cevap
Açıklama: Ya alınır ya alınmaz.
2 Kapasite aşımı
if w > ____:if w > capacity:Açıklama: capacity doğru.
3 Knapsack problemi: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
knapsack |
Sırt çantası |
weight |
Ağırlık |
value |
Değer |
capacity |
Kapasite |