תרמיל 0/1

ממקסם ערך מפריטים המונחים בתרמיל מוגבל־משקל.

ספרw=2 v=3

מוזיקהw=3 v=4

מצלמהw=4 v=5

טלפוןw=5 v=6

קיבולת: 8

שלב 1 מתוך 39

תרמיל 0/1: 4 פריטים, קיבולת = 8. בנה טבלה בגודל (5)×(9) כאשר dp[i][w] = הערך המקסימלי בעזרת i הפריטים הראשונים בקיבולת w.

▶אלגוריתם

Knapsack(items, W):
dp[0][w] = 0 for all w
for i = 1..n, w = 0..W:
if item.weight > w:
  dp[i][w] = dp[i−1][w]
else:
  dp[i][w] = max(dp[i−1][w],
             dp[i−1][w−wt]+v)
backtrack to find selected items

מקרא

התא הנוכחי

תלויות

מסלול אופטימלי

מחושב

dp[i][w] = הערך המקסימלי בעזרת i הפריטים הראשונים בקיבולת משקל w. שורות = פריטים, עמודות = קיבולת.

1 / 39מהירות