מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/רשת החומוסיות/תשובה
ראשית נניח שהמערך M
ממויין, או, לחלופין, נמיין אותו בעזרת מיון מיזוג בסיבוכיות .
נגדיר כ את מירב הרווח שאפשר להרוויח מפתיחת סניפים הלקוחים מתוך הבתים הראשונים.
משפט: לפי הגדרת :
|
הוכחה: (2)
אם , אז ברור שהפתרון הרווחי ביותר הוא זה שבו בוחרים את הבית הראשון (והיחידי האפשרי לבחירה). אם , אז או שבוחרים את בית , או שלא. במקרה הראשון, מרוויחים מהבחירה בבית, אך לפניו אסור לבחור באף בית בעל מיקום שהפרשו מקטן מ. במקרה השני, הרווח הוא בדיוק הרווח כשמותר לבחור מבין הבתים הראשונים.
להלן פסוודו-קוד המממש נוסחה זו.
Max-Profit(M, P, k, i)
1 if i == 0
2 return 0
3 if i == 1
4 return P[1]
5 guess-without = Max-Profit(i - 1)
6 guess-with = P[i]
7 if m[i] > k
8 j = Find-Index(M, M[i] - k)
9 guess-with = guess-with + Max-Profit(M, P, k, j)
10 if guess-with > guess-without
11 return guess-with
12 else
13 return guess-without
חשוב רק לשים לב לקריאה לפונקציה Find-Index
ב8. פונקציה זו מוצאת את האינדקס הגדול ביותר בM
שקטן מM[i] - k
. היות שM
ממויין, נוכל לעשות זאת על ידי שינוי קטן בחיפוש בינרי. נוסיף גם Memoization:
1 MP = Make-Array(n)
2 for i in [1, ..., n]
3 MP[i] = Nil
Max-Profit(M, P, k, i)
1 if i == 0
2 return 0
3 if MP[i] != Nil
4 return MP[i]
5 if i == 1
6 MP[1] = P[1]
7 return P[1]
8 guess-without = Max-Profit(i - 1)
9 guess-with = P[i]
10 if m[i] > k
11 j = Find-Index(M, M[i] - k)
12 guess-with = guess-with + Max-Profit(M, P, k, j)
13 if guess-with > guess-without
14 MP[i] = guess-with
15 return guess-with
16 else
17 MP[i] = guess-without
18 return guess-without
כעת נוסיף גם את הדפסת האיברים:
1 MP = Make-Array(n)
2 Used = Make-Array(n)
3 for i in [1, ..., n]
4 MP[i] = Nil
Max-Profit(M, P, k, i)
1 if i == 0
2 return 0
3 if MP[i] != Nil
4 return MP[i]
5 if i == 1
6 MP[1] = P[1]
7 Used[1] = True
8 return P[1]
9 guess-without = Max-Profit(i - 1)
10 guess-with = P[i]
11 if m[i] > k
12 j = Find-Index(M, M[i] - k)
13 guess-with = guess-with + Max-Profit(M, P, k, j)
14 if guess-with > guess-without
15 MP[i] = guess-with
16 Used[i] = True
17 return guess-with
18 else
19 MP[i] = guess-without
20 Used[i] = False
21 return guess-without
המערך Used
מתאר האם השתמשנו באיבר האו לא. נשתמש בו ע"י קריאה לPrint-Nums(k, n)
, כאשר Print-Nums
מוגדרת כך:
Print-Nums(k, i)
1 if i &lt 1
2 return
3 if Used[i]
4 j = Find-Index(M, M[i] - k)
5 Print-Nums(k, j)
6 else
7 Print-Nums(k, i - 1)
8 if Used[i]
9 Print(i)
נותר רק לנתח את הסיבוכיות.
השורה j ← Find-Index(M, M[i] - k)
אורכת . אם נגדיר כ את זמן הקריאה לMax-Profit(M, P, k, i)
בהנחה שכל קריאה רקורסיבית היא , אז , והסיבוכיות היא . מצד שני, מיון המערך הוא , ולכן נקבל .