Özet - Knapsack
- Algoritmalar kursu
- İleri seviye
- Ders 16/56
- 4 dk
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.
Başlangıç kodu
def knap_print(W, weights, values, n):
# Knapsack yazdırÖrnek çözüm
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)Beklenen çıktı
220
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Knapsack: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
knapsack |
Sırt çantası |
DP |
Tablo |
take |
Al |
skip |
Alma |
2 Ağırlık kontrol
Soru
if weights[i - 1] <= ____:
Cevap
if weights[i - 1] <= w:Açıklama: w doğru.
3 Knapsack hangi alana örnektir?
- Backtracking
- Greedy
- Dinamik programlama Doğru cevap
- Böl ve yönet
Açıklama: Dinamik programlama.