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

ראשית נניח שהמערך תבנית:קוד בשורהממויין, או, לחלופין, נמיין אותו בעזרת מיון מיזוג בסיבוכיות $\mathrm{\Theta }(n\cdot \log (n))$.

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

תבנית:הוכחה

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

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

חשוב רק לשים לב לקריאה לפונקציה תבנית:קוד בשורה ב8. פונקציה זו מוצאת את האינדקס הגדול ביותר בתבנית:קוד בשורהשקטן מתבנית:קוד בשורה. היות שתבנית:קוד בשורהממויין, נוכל לעשות זאת על ידי שינוי קטן בחיפוש בינרי. נוסיף גם 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

המערך תבנית:קוד בשורה מתאר האם השתמשנו באיבר ה$i$או לא. נשתמש בו ע"י קריאה לתבנית:קוד בשורה, כאשר תבנית:קוד בשורה מוגדרת כך:

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)

נותר רק לנתח את הסיבוכיות.

השורה תבנית:קוד בשורהאורכת $O(\log (n))$. אם נגדיר כ$T^{\prime }(i)$ את זמן הקריאה לתבנית:קוד בשורהבהנחה שכל קריאה רקורסיבית היא $O(1)$, אז $T^{\prime }(i)=O(\log (n))$, והסיבוכיות היא $O(n\cdot \log (n))$. מצד שני, מיון המערך הוא $\mathrm{\Omega }(n\cdot \log (n))$, ולכן נקבל $\mathrm{\Theta }(n\cdot \log (n))$.