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

התשובה מתחלקת לשלושה חלקים:

1. הפיכת המערך תבנית:קוד בשורה לעץ.
2. מציאת העומדת בראש החבר.
3. פתרון הבעיה על העץ.ראשית נבנה את העץ המתאר את החברה. קל לעשות זאת. צמתי העץ הם פשוט $\{1,\dots n\}$, וקשתותיו

מתאימים לזוגות שבמערך תבנית:קוד בשורה. אם משתמשים ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]], קל לראות שהסיבוכיות היא $\mathrm{\Theta }(n)$. קל גם למצוא את העומדת בראש החברה. פשוט יש למצוא עבור איזה $s\in \{1,\dots n\}$,‏ $s$ אינו מופיע כאיבר השני באף אחד מהזוגות בתבנית:קוד בשורה. גם שלב זה אורך $\mathrm{\Theta }(n)$. כעת נתבונן בתת-עץ כלשהו, שראשו בצומת $u$, וילדי $u$ הם $v_1,\dots v_i$ (שים לב שכל צומת יכול להיות גם הוא ראשו של תת-עץ בעצמו).

.

.

נגדיר כ$m^{+}(u)$ את הפתרון הטוב ביותר לתת-העץ ששורשו $u$ (הסיבה לסימון המוזר תתבהר בהמשך). בעץ זה, או שנבחר להזמין את $u$, או שלא. אם לא נזמין את $u$, קל להווכח שהפתרון הוא, עפ"י ההגדרה, $\sum _{j=1}^i{m}^{+}(v_j)$. מצד שני, נניח שנבחר להזמין את $u$. האם במקרה זה נוכל בהכרח להזמין $1+\sum _{j=1}^i{m}^{+}(v_j)$? לכאורה כן, מפני ש$u$ עצמו תורם 1 אדם למסיבה, ושאר הביטוי מתאר את הפתרונות הטובים ביותר עבור ילדיו. מצד שני, נוסחה זו לוקחת בחשבון גם מצבים אסורים, בהם אנו מזמינים הן את $u$ והן את אחד מילדיו הישירים. ננסה, אם כן, להגדיר דברים בצורה עדינה יותר. לכל צומת $u$, נגדיר כ$m^{+}(u)$ את הפתרון הטוב ביותר לתת-העץ ששורשו $u$ כאשר מותר (אך לא חייבים) לבחור ב$u$. (נשים לב שהגדרת $u$ לא השתנתה.) נגדיר כ$m^{-}(u)$ את הפתרון הטוב ביותר ל תת-העץ ששורשו $u$ כאשר אסור לבחור ב$u$. קל לחשב רקורסיבית שתי פונקציות אלו, ואחת מהן גם פותרת את הבעיה המקורית. המשפט הבא טוען זאת במדוייק.

• אם ילדי $u$ הם $v_1,\dots v_i$:

$m^{+}(u)=\max \{1+\sum _{j=1}^i{m}^{-}(v_j),\sum _{j=1}^i{m}^{+}(v_j)\}$
הפענוח נכשל (שגיאת תחביר): {\displaystyle \displaystyle m^{-}(u) = <span xmlns="" class="latex">\sum_{j = 1}^im^{+}(v_j)</span> }
אם $s$ שורש העץ, אז הפתרון לבעייתנו הוא $m^{+}(s)$.

תבנית:הוכחה כעת נניח שמותר להזמין את $u$. אז יש שתי אפשרויות: מזמינים אותו, או לא מזמינים אותו. אם לא מזמינים אותו, מקבלים בדיוק את המצב הקודם, דהיינו $\sum _{j=1}^i{m}^{+}(v_j)$. אם מזמינים את $u$ יש להוסיף 1, אך אסור להזמין אף אחד מילדיו הישירים. הטוב ביותר שנוכל לקבל הוא $1+\sum _{j=1}^i{m}^{-}(v_j)$. יש לקחת את הטוב משתי האפשרויות. לכן $m^{+}(u)=\max \{1+\sum _{j=1}^i{m}^{-}(v_j),\sum _{j=1}^i{m}^{+}(v_j)\}$