בעיית Knapsack
פריטים (ערך, נפח):
פריט 1:
פריט 2:
פריט 3:
פריט 4:
ערך | נפח
נפח התרמיל W =
▶ הרץ סימולציה
נוסחה אינדוקטיבית (הרעיון):
T[i,w]
= הערך המקסימלי מ-i הפריטים הראשונים, עם נפח w
לכל w — אין פריטים:
T[0,w] = 0
נפח התרמיל 0:
T[i,0] = 0
אם
w
i
> w
:
T[i,w] = T[i−1, w]
אם
w
i
≤ w
:
T[i,w] = max(T[i−1, w], v
i
+T[i−1, w−w
i
])
פריטים נבחרים
פריט
v
i
w
i
⚠️ עץ הרקורסיה גדול מאוד (יותר מ-150 קריאות). הסימולציה תוצג, אך ייתכן שהעץ יהיה צפוף. מומלץ לבחור פחות פריטים או נפח קטן יותר לצפייה נוחה.
אלגוריתם רקורסיבי
תכנות דינאמי
קריאה ראשונה (טרם הושלמה)
קריאה פעילה
קריאה חוזרת (מחושבת שוב!)
תנאי בסיס / הושלמה
תיאור השלב
לחץ על "הבא" להתחלת הסימולציה
האלגוריתם הרקורסיבי
▶ הקודם
הבא ◀
↺ איפוס
שלב 0/0
c
2
: T[i-1,w]
c
1
: T[i-1,w-w
i
]
ערך נוכחי
חושב
תוצאה T[n,W]
מסלול בחירה
תיאור השלב
לחץ על "הבא" להתחלת הסימולציה
האלגוריתם
▶ הקודם
הבא ◀
↺ איפוס
שלב 0/0