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

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

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

פסוודו-קוד

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

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

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

נוסיף עוד מטריצה גלובלית תבנית:קוד בשורה כך שתבנית:קוד בשורה מתארת את מספר העובדות האופטימלי שכדאי להקצות לפרוייקט ה$i$ אם יש $i$ פרוייקטים ו$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)

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

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

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

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

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

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

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

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

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

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