Knapsack problemi

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.

Örnek çözümü göster

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))

Kendini test et

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
Cevabı göster

Ya alınır ya alınmaz — Ya alınır ya alınmaz.
Kapasite aşımı
```
if w > ____:
```
Cevabı göster
```
if w > capacity:
```
Knapsack problemi: kavramları eşleştir

knapsack

Sırt çantası
weight

Ağırlık
value

Değer
capacity

Kapasite

Sıradaki ders: 0/1 knapsack DP

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler