בפתרון נשתמש במערך גלובלי L המתאר, בכניסה ה, את האיבר הקטן ביותר עד כה המסיים תת-סידרה עולה באורך .
אלה שלבי פעולות הפתרון:
נאתחל את כל אחד מאיברי L ל.
נעבור בלולאה, משמאל לימין, על איברי X. כשנגיע לאיבר ה:
נחפש את האיבר הגדול ביותר ב בL[1], ..., L[i - 1] שאינו גדול מX[i].
אם מצאנו איבר כזה בכניסה ה של L, נקבע L[j + 1] = X[i].
אם לא, נקבע L[1] = X[i].
נמצא את האיבר הגדול ביותר בL שאינו , ונחזיר את האינדקס שלו כתשובה המבוקשת.
דוגמה:
נניח שX == [1, 5, 2, 3].
תחילה נאתחל את המערך L, כך שL == [∞, ∞, ∞, ∞].
כעת נעבור בלולאה על איברי X:
כשi == 1, אז X[i] == 1. בL אין שום איבר קטן מ1 בתחום . נקבע, לכן, L[1] = 1. בשלב זה L = [1, ∞, ∞, ∞].
כשi == 2, אז X[i] == 5. האיבר הגדול ביותר בL שאינו גדול מ5, הוא 1 באינדקס 1. נקבע, לכן, L[2] = 5. בשלב זה L = [1, 5, ∞, ∞].
כשi == 3, אז X[i] == 2. האיבר הגדול ביותר בL שאינו גדול מ2, הוא 1 באינדקס 1. נקבע, לכן, L[2] = 2. בשלב זה L = [1, 2, ∞, ∞,].
כשi == 4, אז X[i] == 3. האיבר הגדול ביותר בL שאינו גדול מ4, הוא 2 באינדקס 2. נקבע, לכן, L[3] = 3. בשלב זה L = [1, 2, 3, ∞].האיבר הגדול ביותר בL שאינו , הוא 3. נחזיר, לכן, את האינדקס שלו - 3.
את המשפט הבא קל להוכיח באינדוקציה:
משפט:
בסוף האיטרציה ה של הלולאה:
L ממוין.
אם האיבר ה בL אינו , אז יש תת-סידרה עולה בX[1], ..., X[i] המסתיימת באיבר שערכו L[j].
ב4-6 מעדכנים את L על פי ההסבר שראינו למעלה. הפונקציה Smaller-Index, שמימושה אינו מופיע כאן, ניתנת למימוש בקלות באופן דומה למה שראינו ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] (שים לב שL ממוין). הסיבוכיות היא .
ב7-10 מחפשים את המקסימום בL. קל לראות שהסיבוכיות לינארית.
נתונה סידרה של מספרים גדולים או שווים ל1. תת-סידרה של X נקראת חברותית אם היא מכילה לפחות שני איברים עוקבים של X, ובדלנית אם היא איננה חברותית.
דוגמה:
נניח ש. אז:
היא תת-סידרה חברותית.
היא תת-סידרה בדלנית.
היא תת-סידרה חברותית.
היא תת-סידרה בדלנית.
היא תת-סידרה בדלנית.
אנא כתוב אלגוריתם אשר מקבל סידרה ומדפיס תת-סידרה בדלנית שמכפלת איבריה גדולה ככל האפשר. (הנח שמכפלת איברי תת-סידרה ריקה היא 1.) קבע את Length(X) כ, ונתח את סיבוכיות האלגוריתם במונחי .
דוגמה:
נניח שהאלגוריתם מקבל כקלט את . במקרה זה, עליו להדפיס : זו תת-סידרה בדלנית של , , ואין תת-סידרה בדלנית אחרת שמכפלת איבריה גדולה מ35.
קל לראות שסיבוכיות האלגוריתם גבוהה מדי. היא נתונה ע"י הפתרון לנוסחה (כלומר אקספוננציאלית, מפני שזו סדרת Fibonacci), וסיבתה היא הסיבה הקבועה: פתירת אותן תת-בעיות שוב ושוב.
המערך U מחזיק בכניסה ה את ההכרעה האם תת-הסדרה הטובה ביותר עד אכן משתמשת באיבר ה או לא.
קטע הקוד הבא מראה כיצד להדפיס את האינדקסים של תת-הסידרה הטובה ביותר המסתיימת ב.
נתונה פיסת בד שמידותיה (כלומר ארכה מטר, ורחבה מטר). הנח ש ו
מספרים שלמים.
נתונות מידות,
,
שלהן מותאמים מחירים . כלומר:
חתיכת בד במידה שווה שקלים.
חתיכת בד במידה שווה שקלים.
...
חתיכת בד במידה שווה שקלים.חוץ מ מידות אלה, כל המידות האחרות חסרות ביקוש, ולכן כל חתיכת בד במידה שונה
ממידות אלה שווה 0 שקלים. הנח שכל ו הוא מספר שלם חיובי ממש.
דוגמה:
בתרשים הבא, A מראה פיסת בד במידות , וB מראה שתי מידות בעלת ערך: העליונה
בעלת המידות , והתחתונה בעלת המידות . נניח שהמידה העליונה שווה 35 שקל, והתחתונה שווה 2 שקלים.
.
המטרה היא להפיק מהבד את מרב הערך, ע"י גזירת הבד אם יש תועלת
בכך. בכל גזירה אפשר מותר לגזור את פיסת הבד לאורך או לרוחב. הנח
שאין יכולת לסובב את פיסת הבד.
דוגמה:
כיצד נוכל להשתמש בפיסת הבד מA שבדוגמה הקודמת? לו היינו
יכולים לסובב אותה, היינו יכולים להפיק ממנה צורה ששווייה 35
שקל ללא גזירה אחת. עם זאת, עדיין יש סדרת גזירות שתפיק צורות
בשווי 4 שקלים.
בתרשים הבא:
A מראה את החתך הראשון: נחתוך את הצורה אנכית בשורה 1, ונקבל את שתי הצורות בB.
את הצורה העליונה בB נחתוך אנכית בטור הראשון, ונקבל את שלוש הצורות בC.
את הצורה התחתונה בC נחתוך אנכית בטור 2, ונקבל את ארבע הצורות בD.
כל אחת מהשורות בD מכילה כעת צורה אחת ששווייה 2 שקלים, ועוד צורה חסרת ערך.
.
יש עוד סדרות חיתוך שיניבו צורות בשווי 4 שקלים, אך אין סדרה שתניב יותר מכך.
בשאלה זו עליך למצוא אלגוריתם יעיל למציאת סדרת החיתוך הרווחית ביותר. אנא הוכח שהאלגוריתם שמצאת עובד בסיבוכיות .
הנח שקיימת פונקציה Value(i, j) המחזירה בזמן :
0 אם אינה אחת מ המידות בעלות התועלת.
אם .
כדאי לדעת:
אפשר לפתור את הבעיה בצורה הבאה. מכינים טבלה בגודל על ובתא ה- שמים את הרווח מחיתוך הבד לגודל . רווח זה יהיה המקסימום מהרווחים אותם אפשר להשיג מחיתוך הבד לרוחב, מחיתוך הבד לאורך, וממכירת הבד כפי שהוא (כפי שמוחזר מהפונקציה Value(i, j)).
שים לב שהנוסחה הנ"ל כוללת בתוכה תנאי עצירה, מפני שעבור , מה שכתוב כאן הינו פשוט .
אפשר גם לכתוב את נוסחת הנסיגה בדרכים אחרות, ובחלקן גם יופיעו תנאי עצירה בצורה מפורשת יותר.
הוכחה: יש שלוש אפשרויות:
כדאי לחתוך את פיסת הבד אפקית באיזשהו (כמתואר בתרשים הבא). נשים לב שאפשרות זו רלוונטית רק עבור עבור .
כדאי לחתוך את פיסת הבד אנכית באיזשהו (כמתואר בתרשים הבא אחריו). נשים לב שאפשרות זו רלוונטית רק עבור עבור .
כלל לא משתלם לחתוך את פיסת הבד.
בתרשים הבא, לדוגמה, חיתוך אופקי של הצורה בA בשורה ייצור שתי צורות מלבניות בB; לראשונה שבהן יהיו שורות:
חיתוך אופקי.
בתרשים הבא, לדוגמה, חיתוך אנכי של הצורה בA בעמודה ייצור שתי צורות מלבניות בB; לראשונה שבהן יהיו עמודות:
חיתוך אנכי.
כעת נדון בכל אחת משלוש האפשרויות:
כדאי לחתוך את פיסת הבד אפקית באיזשהו . במקרה זה נקבל שתי חתיכות בד, האחת במידות , והשניה במידות . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא , ועבור השניה .
כדאי לחתוך את פיסת הבד אנכית באיזשהו . במקרה זה נקבל שתי חתיכות בד, האחת במידות , והשניה במידות . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא , ועבור השניה .
כלל לא משתלם לחתוך את פיסת הבד: הטוב ביותר האפשרי הוא Value(i, j).
היות שאיננו יודעים איזו משלוש האפשרויות היא הטובה ביותר, אנו לוקחים את המקסימום מבין שלושתן.
שוב כרגיל, כדי לשמור גם את סדרת הפעולות (ולא רק תוצאתן), נוסיף עוד מבנה נתונים פשוט (במקרה זה המטריצה C):
1M=Make-Matrix(m,n)2C=Make-Matrix(n,n)3foriin[1,...,m]4forjin[1,...,n]5M[i][j]=Nil6C[i][j]=NilMax-Value(i,j)1ifM[i,j]!=Nil2returnM[i,j]3max-value=0# Check horizontal cuts.4fori' in [1, ..., i - 1]5guess=Max-Value(i', j) + Max-Value(i - i',j)6ifguess>max-value7max-value=guess8C[i][j]=('Horizontal',i')# Check vertical cuts.9forj' in [1, ..., j - 1]10guess=Max-Value(i,j') + Max-Value(i, j - j')11ifguess>max-value12max-value=guess13C[i][j]=('Vertical',j')# Check the worth of this shape.14guess=Value(i,j)15ifguess>max-value16max-value=guess17C[i][j]=('Shape',0)18M[i,j]=max-value19returnmax-value
המטריצה C היא מטריצה של זוגות (בשפת C היינו ממשים זאת בעזרת מטריצה של מבנים):
האיבר הראשון בכל זוג הוא מחרוזת, המתארת איזו משלוש האפשרויות היא בחרנו.
האיבר השני בכל זוג הוא מספר המתאר היכן חתכנו.
הנה הקוד המדפיס את סדרת הפעולות:
Print-Cuts(i,j)1Print('For the best value of '+i+' and '+j)2(type,index)=C[i][j]3iftype=='Horizontal'4Print'Cut horizontally at '+index5Print-Cuts(index,j)6Print-Cuts(i-index,j)7elseiftype=='Vertical'8Print'Cut vertically at '+index9Print-Cuts(i,index)10Print-Cuts(i,j-index)11else12Print'Use the shape itself'
נגדיר כ את אורך הLCS של ו. במילים אחרות, היא אורך תת-הסדרה הארוכה ביותר המשותפת ל ו.
עכשיו תורכם:
וודא שהמך מבין מדוע לפי הגדרה זו, הוא אורך הLCS של ו.
משפט:
מקיים את הנוסחה הבאה:
אם או , אז .
אם לא, אז:
אם , אז .
אם , אז .
הוכחה: אם או , אז (לפחות) אחת המחרוזות היא המחרוזת הריקה, ורק המחרוזת הריקה יכולה להיות תת-מחרוזת של המחרוזת הריקה. למחרוזת הריקה יש אורך 0, ומכאן החלק הראשון של המשפט.
מכאן נניח ששתי המחרוזות אינן ריקות.
נניח ש. ראשית, קל לראות שבהכרח תווה האחרון של הוא - אם זה לא היה המצב, אז גם היא מחרוזת משותפת ל ו, דבר שנוגד עפ"י ההגדרה את היותה של תת-המחרוזת המשותפת הארוכה ביותר. נחשוב כעת על כל תתי המחרוזות המשותפות מהצורה : עבור כל אחת מהן, קל לראות ש היא תת-מחרוזת משותפת ל ו, ולכן בהכרח הארוכה שבהן היא זו שהרישה שלה היא הLCS של ו.
לחלופין, נניח ש; יש שלוש אפשרויות:
מסתיימת ב - אם כן, הLCS בהכרח מהצורה , כאשר היא הLCS של ו.
מסתיימת ב - אם כן, הLCS בהכרח מהצורה , כאשר היא הLCS של ו.
אינה מסתיימת ב, וכן אינה מסתיימת ב - אם זה המצב, אז הLCS של ו הוא הLCS של ו (וכן גם הLCS של ו), כך ששתי הבדיקות הקודמות מכסות כבר (פעמיים אפילו) מקרה זה.
ארבע השורות הראשונות מאתחלות מטריצה המשמשת לmemoization, והפונקציה LCS-Length מוצאת את את האורך המבוקש. 1-4 מייצרות מטריצה (גלובלית) שכל אחד מאיבריה מאותחל לNil. 2-9 של LCS-Length, פועלות בדיוק לפי נוסחת הנסיגה הקודמת (שאת נכונותה כבר הראינו). המטריצה L, בפרט ב1 של LCS-Length, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה בעבר.
קל לראות שהסיבוכיות עדיין : השינויים בLCS-Length אינם משנים את סיבוכיותה; כל קריאה לPrint-LCS(i, j) מורידה (לפחות) את אחד הארגומנטים שלה ב1, ולכן היא יכולה להיקרא לכל היותר פעמים. הסיבוכיות, לכן, היא + = .
מעל הירקון עומד גשר שאורכו מטרים ( מספר שלם חיובי גדול מ1 כלשהו). הגשר נמצא לא תקין אפילו בסטנדרטים של מדינת ישראל(!). יש לפרק את הגשר לחלקים ולפנותו בצורה הזולה ביותר. ראשית צריך לשבור את הגשר. ניתן לשבור את הגשר למספר חלקים. שבירת הגשר חייבת להתבצע בנקודות בלבד. שבירת כל נקודה עולה שקלים ( מספר שלם חיובי כלשהו).
דוגמה:
נניח ו (ראה A בתרשים הבא). אפשר לשבור את הגשר ב4 אפנים:
שוברים בנקודות 1 ו2. מתקבלים 3 חלקים בעלי אורך 1 כל אחד (ראה B בתרשים הבא). עלות השבירה היא .
שוברים בנקודה 1. מתקבלים 2 חלקים: הראשון בעל אורך 1, והשני בעל אורך 2 (ראה C בתרשים הבא). עלות השבירה היא .
שוברים בנקודה 2. מתקבלים 2 חלקים: הראשון בעל אורך 2, והשני בעל אורך 1 (ראה D בתרשים הבא). עלות השבירה היא .
לא שוברים באף נקודה. מתקבל חלק יחיד בעל אורך 3. עלות השבירה היא .
דוגמה לגשר הזבלה.
כעת יש להוביל את חלקי הגשר. הנח שקיימת פונקציה ידועה כך ש מתארת את עלות הובלתו של חלק בעל אורך i. הנח ש הוא מספר שלם חיובי לכל .
שימו לב:
וודא שאינך מניח במובלע דברים שלא נאמרו לגבי . בפרט, אל תניח שהפונקציה מונוטונית עולה (עלות ההובלה נקבעת לפי שיקולים שאיננו יודעים.)
דוגמה:
בהמשך לדוגמה הקודמת שראינו, נניח , , ו. ארבע האפשרויות שראינו מקודם יעלו כך:
עלות ההובלה היא .
עלות ההובלה היא .
עלות ההובלה היא .
עלות ההובלה היא .
אנא מצא אלגוריתם יעיל למציאת נקודות השבירה כך שסך העלויות (שבירה והובלה) נמוך ככל האפשר. כלומר, אנא כתוב אלגוריתם יעיל שימצא את העלות המינימלית וכן ידפיס את נקודות השבירה של עלות זו.
אם , אז או שלא חותכים את הקטע, או שכן. אם לא חותכים, עלות השבירה 0, ועלות ההובלה . אם חותכים בנקודה , אז עלות הטיפול בחלק השמאלי תהיה , עפ"י ההגדרה, , עלות השבירה היא כמובן , ועלות הטיפול בחלק הימני תהיה, עפ"י ההגדרה, . נותר לקחת מינימום על פני , ולהחליט האם לחתוך או לא.
כדאי לדעת:
אפשר כמובן לחשוב על מבנה רקורסיבי אחר לבעיה, כמו לדוגמה המבנה בדג הסלמון.
הפונקציה מקבלת שני ארגומנטים: אורך הקטע, i, ותחילת הקטע, start. נניח שהפונקציה נקראה עבור שני ערכים ספיציפיים כאלה. אם Break[i] == Nil, אז לא חתכנו את הקטע, ואין מה להדפיס. אם לא, וBreak[i] == j, אז יש להדפיס את הנקודה j(תוך זכירה שאנו נמצאים startמתחילת כל הגשר), את החלק השמאלי, ואת החלק הימני.
נצייר את עץ הקריאות הרקורסיביות, תוך לקיחה בחשבון את נושא הmemoization.
עץ הקריאות הרקורסיביות.
הציור אינו מראה את כל צמתי הקריאה מטעמי נוחות. הצומת קורא לצומת , בעקיפין לצמתים ו, ולעוד צמתים. הקווים המקווקווים מציינים שהקריאות אינן בהכרח ישירות.
חלק מהצמתים מודגשים, וחלק אינם:
צומת מודגש אם הוא מתאר קריאה "רצינית", כלומר אחת שבה החלק העיקרי בפונקציה מתבצע (שורות 3-11 בMin-Time).
צומת אינו מודגש אם הוא מתאר קריאה "פושטית", בה לכל היותר רק חלק הmemoization מתבצע (שורות 1-2 בMin-Time).
נשים לב לנקודות הבאות:
אם צומת לא מודגש, אז אין לו ילדים, ובנוסף, הוא (מדוע?)
כל צומת מופיע מודגש פעם אחת (מדוע?)
ננתח כעת בשלבים, לפי הרעיון הבא. בכל שלב:
ניקח צומת מודגש שאין לו ילדים מודגשים.
ננתח את זמן הריצה שלו, ונרשום את התוצאה בצד. נשים לב שאם לצומת אין ילדים מודגשים, אז כל קריאה רקורסיבית שלו היא אכן (מפני שזו איננה ממש קריאה רקורסיבית). זמן הריצה שלו, לכן, הוא אכן .
נמיר אותו בצומת לא מודגש, מפני שניתחנו כבר את חלק הקוד המסובך בו (ורשמנו אותו בצד). כל שנותר הוא הקריאה לפונקציה, והיא לוקחת .
נתחיל בצומת המודגש. לצומת זה אין כלל ילדים, ולכן זמן הקריאה הוא בבירור .
נרשום בצד שעד כה הקריאות שעברנו עליהן עלו , ונחליף את הצומת בצומת לא מודגש. זה מסמן את העובדה שניתחנו כבר את החלק "עם הבשר" בצומת , וכל שנותר הוא .
עץ הקריאות הרקורסיביות - שלב 1.
נחזור על אותה הפעולה עבור הצומת .
עץ הקריאות הרקורסיביות - שלב 2.
כנ"ל לגבי הצומת .
עץ הקריאות הרקורסיביות - שלב 3.
כעת נתבונן בצומת בשלב בו כל ילדיו אינם מודגשים. כל קריאה רקורסיבית של צומת זה כוללת שני מחירים:
עצם הקריאה לפונקציה, שעולה
זמן הקריאה האמיתי, שאותו כבר חייבנו (ורשמנו בצד), ולכן אין צורך לחייב אותו כאן שוב
הפועל היוצא הוא שבשלב זה, מותר לנו לחייב את הצומת אך ורק בקריאות רקורסיביות שעלות כל אחת מהן היא . זה בדיוק .
קל להשתכנע שבשלב בו נחליף את צומת הראש בצומת לא מודגש, רשמנו בצד את כל האיברים מהצורה
,
כאשר
ו. בצורה אחרת, מה שרשום בצד הוא
.
(הנוסע המתמיד האוקלידי)
נתונות נקודות במישור. כל נקודה מייצגת שדה תעופה, לצורך העניין. סוכן נסיעות מתחיל את מסלולו בשדה התעופה השמאלי ביותר; עליו לעבור בכל שדה תעופה ולנחות בשדה התעופה שממנו יצא לדרכו. מחיר הטיסה משדה תעופה אחד לשני הוא המרחק האוקלידי בין שני השדות. על הנוסע למצוא את המסלול שעלותו הכוללת נמוכה ככל האפשר.
כדאי לדעת:
לבעיית הנוסע המתמיד האוקלידי אין אלגוריתם יעיל ידוע - כל האלגוריתמים הידועים עובדים בזמן אקספוננציאלי. למרות שהדבר לא הוכח, יש סיבות המרמזות לכך שלא ייתכן אלגוריתם יעיל לבעיה זו.
שאלה זו דנה בגרסה קלה יותר של הבעיה.
הגדרה:
(מסלול ביטוני)
מסלול הוא ביטוני אם הוא מורכב משני תתי מסלולים: בראשון נעים בכיוון ימין, ובשני נעים מימין חזרה לכוון שמאל.
דוגמה:
בתרשים הבא, A מראה מישור בעל נקודות; B מראה את המסלול הקצר ביותר, אך המסלול אינו ביטוני.
מישור ומסלולים.
בתרשים הבא, A וB מראים כל אחד מסלול ביטוני אפשרי.
מסלולים ביטוניים.
בשאלה זו עליך למצוא אלגוריתם למציאת המסלול הביטוני האוקלידי הזול ביותר לכל קבוצת נקודות במרחב: אנא תאר אלגוריתם יעיל המוצא את עלות המסלול הנמוכה ביותר.
שימו לב:
#הנח שP הוא מערך גלובלי בעל אורך המתאר את הנקודות.
כדי לגשת לקואורדינטות הX והY של הנקודה ה, השתמש בP[i].x ובP[i].y, בהתאמה.
הנח שP ממוין בסדר עולה על פי קואורדינטות הX של נקודותיו (ולכן P[1] היא בהכרח נקודת המוצא של הנוסע, לדוגמה).
הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ פונה ימינה, אינו מגיע לאף נקודה אחרת מכוון ימין, ומכסה את כל הנקודות משמאלה ל. לכן, בהכרח, מדובר במסלול שעובר נקודה אחרי נקודה מ ל.
הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ ימינה ל, ומכסה את כל הנקודות משמאלה ל. נסמן כ את הנקודה שאליה עובר המסלול ישירות מ; A בתרשים הבא מציג זאת. מקרה 2 בהוכחת נוסחת הנסיגה. היות שהוכחנו למעלה שלמסלולים שקולים יש מחיר זהה, נוכל לטעון שB בתרשים הקודם בעל אותו מחיר כA.
הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ ימינה ל, ומכסה את כל הנקודות משמאלה ל. היות ש, המסלול חייב להתחיל במעבר ישיר (שמאלה) מ ל. מקרה 3 בהוכחת נוסחת הנסיגה.
רשת החומוסיות מק-לאפה מתכננת להקים סניפים רבים לאורך רחוב איבן-גבירול בתל אביב. מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:
מסקר שוק, הרשת מעריכה שבבית מספר רווחיה הצפויים יהיו ( הוא מספר חיובי כלשהו).
הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ ( הוא מספר שלם חיובי כלשהו).
דוגמה:
אם והרשת בוחרת להקים סניף בבית מספר 135, אסור לה להקים סניף בבית מספר 143, שכן .
אנא כתוב אלגוריתם יעיל המקבל את המערך M (המכיל את מספרי הבתים), את המערך P (המכיל את הרווחים הצפויים), ואת המספר k (המציין את מגבלת המרחק), ומדפיס את מספרי הבתים שהקמת הסניפים בהם צפוייה למקסם את הרווחיות. אנא הוכח נכונות ונתח סיבוכיות.
ראשית נניח שהמערך Mממויין, או, לחלופין, נמיין אותו בעזרת מיון מיזוג בסיבוכיות .
נגדיר כ את מירב הרווח שאפשר להרוויח מפתיחת סניפים הלקוחים מתוך הבתים הראשונים.
משפט:
לפי הגדרת :
הפתרון הטוב ביותר הוא בעל רווח .
הפונקציה נתונה על ידי נוסחת הנסיגה:
לכל ,
מונוטונית לא-יורדת ב.
הוכחה: (2)
אם , אז ברור שהפתרון הרווחי ביותר הוא זה שבו בוחרים את הבית הראשון (והיחידי האפשרי לבחירה). אם , אז או שבוחרים את בית , או שלא. במקרה הראשון, מרוויחים מהבחירה בבית, אך לפניו אסור לבחור באף בית בעל מיקום שהפרשו מקטן מ. במקרה השני, הרווח הוא בדיוק הרווח כשמותר לבחור מבין הבתים הראשונים.
חשוב רק לשים לב לקריאה לפונקציה Find-Index ב8. פונקציה זו מוצאת את האינדקס הגדול ביותר בMשקטן מM[i] - k. היות שMממויין, נוכל לעשות זאת על ידי שינוי קטן בחיפוש בינרי. נוסיף גם Memoization:
השורה j ← Find-Index(M, M[i] - k)אורכת . אם נגדיר כ את זמן הקריאה לMax-Profit(M, P, k, i)בהנחה שכל קריאה רקורסיבית היא , אז , והסיבוכיות היא . מצד שני, מיון המערך הוא , ולכן נקבל .
בבעיית "תכנון הפרוייקטים" יש פרוייקטים ו עובדות. צריך להחליט כמה עובדות יש להקצות לכל אחד מהפרוייקטים.
לכל פרוייקט ומספר עובדות , הוא מספר המייצג את איכות ביצוע הפרוייקט הi אם ישבצו לו עובדות. הנח:
פונקציה לא שלילית (אין איכות שלילית).
מונוטונית לא-יורדת ב (הוספת עובדות לפרוייקט אינה מורידה מאיכותו).
ניתן להקצות 0 עובדות לפרוייקט.
כל עובדת מוקצת לפרוייקט אחד בדיוק.
לכל פרוייקט יש "חשיבות" לא-שלילית . אנו רוצים למקסם את סך האיכויות המשוקללות. במילים אחרות, אנו רוצים למקסם את
.
אנא הצע אלגוריתם יעיל לפתרון הבעיה, כלומר אלגוריתם שימצא את הסכום הנ"ל המקסימלי וכן ידפיס את אופן הקצאת העובדות לכל פרוייקט.
הנח שq(i, j) וh(i) הן פונקציות נתונות לך, שעלות קריאה להן היא .
נגדיר את כאיכות המשוקללת הגבוהה ביותר האפשרית כאשר יש עובדות ו פרוייקטים.
משפט:
=
, אם .
, אם .
הוכחה: אם יש פרוייקט יחיד, אז ברור שכדאי להקצות את כל העובדות לו (שהרי נתון שהוספת עובדות אינה יכולה להוריד את איכות הפרוייקט). לכן, אם יש פרוייקט יחיד ו עובדות, נקבל שאיכותו הטובה ביותר היא .
נניח שיש
פרוייקטים. אם נקצה עובדות לפרוייקט ה, אז איכות הפרוייקט תהיה
,
ונוותר עם עובדות. על פי הגדרתנו, הוא הטוב ביותר שנוכל להשיג במקרה זה.
הפסוודו-קוד הרקורסיבי שמימש את הנוסחה הרקורסיבית, פותר אותן בעיות שוב ושוב. נייצר מטריצה גלובלית M שתשמור את התוצאות שקיבלנו, ונאתחל איברי מטריצה זו לNil. הפסוודו-קוד הבא מראה את השימוש במטריצה M. לשם הפשטות, השמטנו את חלקי הקוד המעדכנים את המטריצה המשמשת להדפסת ההשמות.
Max-Value(i,j)1ifi==12M[1][j]=h(1)q(1,j)3returnh(1)q(1,j)4max-value=05forj' in [0, ..., j]6guess=Max-Value(i-1,j-j') + h(i) q(i, j')7ifguess>max-value8M[i][j]=guess9max-value=guess10returnmax-value