מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תכנון פרוייקטים/תשובה
המבנה הרקורסיבי
[עריכה]נגדיר את כאיכות המשוקללת הגבוהה ביותר האפשרית כאשר יש עובדות ו פרוייקטים.
משפט: =
|
הוכחה: אם יש פרוייקט יחיד, אז ברור שכדאי להקצות את כל העובדות לו (שהרי נתון שהוספת עובדות אינה יכולה להוריד את איכות הפרוייקט). לכן, אם יש פרוייקט יחיד ו עובדות, נקבל שאיכותו הטובה ביותר היא .
נניח שיש
פרוייקטים. אם נקצה עובדות לפרוייקט ה, אז איכות הפרוייקט תהיה
,
ונוותר עם עובדות. על פי הגדרתנו, הוא הטוב ביותר שנוכל להשיג במקרה זה.
פסוודו-קוד
[עריכה]נתרגם את נוסחת הנסיגה הקודמת לפסוודו-קוד.
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]
מתארת את מספר העובדות האופטימלי שכדאי להקצות לפרוייקט ה אם יש פרוייקטים ו עובדות.
להלן הקוד המכיל את השינויים הנדרשים:
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
ניתוח סיבוכיות
[עריכה]כרגיל, נגדיר את
כזמן הריצה של
Max-Value(i, j)
כאשר כל קריאה רקורסיבית היא . קל לראות שמתקיים
כרגיל, נמצא את זמן הריצה האמיתי של הקריאות הרקורסיביות כך:
יש לקחת בחשבון גם את זמן הריצה של אתחול המטריצה (M
ואת הדפסת פרטי הפתרון:
- אתחול המטריצה אורך
- הדפסת הפרטים אורכת
הסיבוכיות הכוללת, לכן, היא