מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/רשת החומוסיות/תשובה

ראשית נניח שהמערך Mממויין, או, לחלופין, נמיין אותו בעזרת מיון מיזוג בסיבוכיות $\displaystyle \Theta (n\cdot \log(n))$ .

נגדיר כ $\displaystyle mp(i)$ את מירב הרווח שאפשר להרוויח מפתיחת סניפים הלקוחים מתוך $\displaystyle i$ הבתים הראשונים.

משפט:

לפי הגדרת $\displaystyle mp(i)$ :

הפתרון הטוב ביותר הוא בעל רווח $\displaystyle mp(n)$ .
הפונקציה נתונה על ידי נוסחת הנסיגה:
- $\displaystyle mp(1)=p_{1}$
- לכל $\displaystyle i>1$ ,‏ $\displaystyle mp(i)=\max \left\{p_{i}+\max _{j|m_{i}-m_{j}>k}mp(j),mp(i-1)\right\}$
$\displaystyle mp(i)$ מונוטונית לא-יורדת ב $\displaystyle i$ .

הוכחה: (2) אם $\displaystyle i=1$ , אז ברור שהפתרון הרווחי ביותר הוא זה שבו בוחרים את הבית הראשון (והיחידי האפשרי לבחירה). אם $\displaystyle i>1$ , אז או שבוחרים את בית $\displaystyle i$ , או שלא. במקרה הראשון, מרוויחים $\displaystyle p_{i}$ מהבחירה בבית, אך לפניו אסור לבחור באף בית בעל מיקום שהפרשו מ $\displaystyle m_{i}$ קטן מ $\displaystyle k$ . במקרה השני, הרווח הוא בדיוק הרווח כשמותר לבחור מבין $\displaystyle i-1$ הבתים הראשונים.

להלן פסוודו-קוד המממש נוסחה זו.

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 מתאר האם השתמשנו באיבר ה $\displaystyle i$ או לא. נשתמש בו ע"י קריאה לPrint-Nums(k, n), כאשר Print-Nums מוגדרת כך:

Print-Nums(k, i)
1	if i &amp;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)אורכת $\displaystyle O(\log(n))$ . אם נגדיר כ $\displaystyle T'(i)$ את זמן הקריאה לMax-Profit(M, P, k, i)בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$ , אז $\displaystyle T'(i)=O(\log(n))$ , והסיבוכיות היא $\displaystyle O(n\cdot \log(n))$ . מצד שני, מיון המערך הוא $\displaystyle \Omega (n\cdot \log(n))$ , ולכן נקבל $\displaystyle \Theta (n\cdot \log(n))$ .