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

המבנה הרקורסיבי

נגדיר את $\displaystyle m(i,j)$ כאיכות המשוקללת הגבוהה ביותר האפשרית כאשר יש $\displaystyle j$ עובדות ו$\displaystyle i$ פרוייקטים.

משפט: $\displaystyle m(i,j)$ = $\displaystyle h(1)q(1,j)$, אם $\displaystyle i=1$. $\displaystyle \max _{j'\;|0\leq j'\leq j}\left[h(i)q(i,j')+m(i-1,j-j')\right]$, אם $\displaystyle i>1$.

הוכחה: אם יש פרוייקט יחיד, אז ברור שכדאי להקצות את כל העובדות לו (שהרי נתון שהוספת עובדות אינה יכולה להוריד את איכות הפרוייקט). לכן, אם יש פרוייקט יחיד ו$\displaystyle j$ עובדות, נקבל שאיכותו הטובה ביותר היא $\displaystyle q(1,j)$.

נניח שיש $\displaystyle i>1$ פרוייקטים. אם נקצה $\displaystyle j'$ עובדות לפרוייקט ה$\displaystyle i$, אז איכות הפרוייקט תהיה $\displaystyle q(i,j')$, ונוותר עם $\displaystyle j-j'$ עובדות. על פי הגדרתנו, $\displaystyle m(i-1,j-j')$ הוא הטוב ביותר שנוכל להשיג במקרה זה.

פסוודו-קוד

נתרגם את נוסחת הנסיגה הקודמת לפסוודו-קוד.

Max-Value(i, j)
1	if i == 1
2		return h(1) q(1, j)

3	max-value = 0
4	for j' in [0, ..., j]
5		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
6		if guess > max-value
7			max-value = guess

8	return max-value

הדפסת פרטי הפתרון

נוסיף עוד מטריצה גלובלית A כך שA[i][j] מתארת את מספר העובדות האופטימלי שכדאי להקצות לפרוייקט ה$\displaystyle i$ אם יש $\displaystyle i$ פרוייקטים ו$\displaystyle j$ עובדות.

להלן הקוד המכיל את השינויים הנדרשים:

Max-Value(i, j)
1	if i == 1
2		A[1][j] = j
3		return h(1) q(1, j)

4	max-value = 0
5	for j' in [0, ..., j]
6		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
7		if guess > max-value
8			A[i][j] = j'
9			max-value = guess

10	return max-value

כעת נשתמש במטריצה כדי להדפיס את האלוקציות האופטימליות:

Print-Assignments(i, j)
1	if i == 0
2		return

	# The optimal assignment assigns j' workers to project i.
3	j' = A[i][j] 

4	Print('Assign ' + j' + ' workers to project ' + i)

5 	Print-Assignments(i - 1, j - j')

כך נפעיל את שתי הפונקציות:

1	A = Make-Matrix(k, n)

2	max-value = Max-Value(k, n)

3	Print(max-value)

4	Print-Assignments(k, n)

הוספת תזכור (memoization)

הפסוודו-קוד הרקורסיבי שמימש את הנוסחה הרקורסיבית, פותר אותן בעיות שוב ושוב. נייצר מטריצה גלובלית M שתשמור את התוצאות שקיבלנו, ונאתחל איברי מטריצה זו לNil. הפסוודו-קוד הבא מראה את השימוש במטריצה M. לשם הפשטות, השמטנו את חלקי הקוד המעדכנים את המטריצה המשמשת להדפסת ההשמות.

Max-Value(i, j)
1	if i == 1
2		M[1][j] = h(1) q(1, j)
3		return h(1) q(1, j)

4	max-value = 0
5	for j' in [0, ..., j]
6		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
7		if guess > max-value
8			M[i][j] = guess
9			max-value = guess

10	return max-value

ניתוח סיבוכיות

כרגיל, נגדיר את $\displaystyle T'(i,j)$ כזמן הריצה של Max-Value(i, j) כאשר כל קריאה רקורסיבית היא $\displaystyle O(1)$. קל לראות שמתקיים $\displaystyle T'(i,j)=\Theta (j)$

כרגיל, נמצא את זמן הריצה האמיתי של הקריאות הרקורסיביות כך:

$\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}[T'(i,j)]=$
$\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}[\Theta (j)]=$
$\displaystyle \sum _{i=1}^{k}[\Theta (n^{2})]=$
$\displaystyle \Theta (k\cdot n^{2}).$

יש לקחת בחשבון גם את זמן הריצה של אתחול המטריצה (M ואת הדפסת פרטי הפתרון:

• אתחול המטריצה אורך$\displaystyle \Theta (k\cdot n)$
• הדפסת הפרטים אורכת $\displaystyle \Theta (k)$

הסיבוכיות הכוללת, לכן, היא

$\displaystyle \Theta (k\cdot n)+\Theta (k)+\Theta (k\cdot n^{2})=\Theta (k\cdot n+k+k\cdot n^{2})=\Theta (k\cdot n^{2})$