Özet - Knapsack

Knapsack çözüp en iyi değeri yazdıran mini görev yaparsın.

Özet - Knapsack

0/1 knapsack; iki boyutlu DP tablosu ve al/alma kararıyla en yüksek değeri bulur. Kaynak tahsisi ve yatırım kararlarında kullanılır.

Bu mini görevde knapsack çözüp en iyi değeri yazdıracaksın; tüm adımları birleştir.

0/1 knapsack Θ(nW) zaman verir; W büyükse sözde polinomsal olarak adlandırılır.

Uygulama Knapsack yazdır

knap_print(W, weights, values, n) yaz. DP ile en yüksek değeri print() ile yazdır. knap_print(50, [10, 20, 30], [60, 100, 120], 3) çıktısı: 220.

Örnek çözümü göster

def knap_print(W, weights, values, n):
    # Knapsack yazdır
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    print(dp[n][W])
knap_print(50, [10, 20, 30], [60, 100, 120], 3)

Kendini test et

Özet - Knapsack: kavramları eşleştir

knapsack

Sırt çantası
DP

Tablo
take

Al
skip

Alma

Ağırlık kontrol

if weights[i - 1] <= ____:

Cevabı göster

if weights[i - 1] <= w:

Knapsack hangi alana örnektir?
- Backtracking
- Greedy
- Dinamik programlama
- Böl ve yönet
Cevabı göster

Dinamik programlama — Dinamik programlama.

Sıradaki ders: Proje: Genel bakış

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler