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

מעל הירקון עומד גשר שאורכו $\displaystyle m$ מטרים ($\displaystyle m$ מספר שלם חיובי גדול מ1 כלשהו). הגשר נמצא לא תקין אפילו בסטנדרטים של מדינת ישראל(!). יש לפרק את הגשר לחלקים ולפנותו בצורה הזולה ביותר. ראשית צריך לשבור את הגשר. ניתן לשבור את הגשר למספר חלקים. שבירת הגשר חייבת להתבצע בנקודות $\displaystyle 1,\cdots ,m-1$ בלבד. שבירת כל נקודה עולה $\displaystyle k$ שקלים ($\displaystyle k$ מספר שלם חיובי כלשהו).

דוגמה: נניח $\displaystyle m=3$ ו$\displaystyle k=100$ (ראה A בתרשים הבא). אפשר לשבור את הגשר ב4 אפנים: שוברים בנקודות 1 ו2. מתקבלים 3 חלקים בעלי אורך 1 כל אחד (ראה B בתרשים הבא). עלות השבירה היא $\displaystyle 2\cdot 100=200$. שוברים בנקודה 1. מתקבלים 2 חלקים: הראשון בעל אורך 1, והשני בעל אורך 2 (ראה C בתרשים הבא). עלות השבירה היא $\displaystyle 1\cdot 100=100$. שוברים בנקודה 2. מתקבלים 2 חלקים: הראשון בעל אורך 2, והשני בעל אורך 1 (ראה D בתרשים הבא). עלות השבירה היא $\displaystyle 1\cdot 100=100$. לא שוברים באף נקודה. מתקבל חלק יחיד בעל אורך 3. עלות השבירה היא $\displaystyle 0\cdot 100=0$. דוגמה לגשר הזבלה.

כעת יש להוביל את חלקי הגשר. הנח שקיימת פונקציה $\displaystyle f$ ידועה כך ש$\displaystyle f(i)$ מתארת את עלות הובלתו של חלק בעל אורך i. הנח ש$\displaystyle f(i)$ הוא מספר שלם חיובי לכל $\displaystyle i$.

שימו לב: וודא שאינך מניח במובלע דברים שלא נאמרו לגבי $\displaystyle f(i)$. בפרט, אל תניח שהפונקציה מונוטונית עולה (עלות ההובלה נקבעת לפי שיקולים שאיננו יודעים.)

דוגמה: בהמשך לדוגמה הקודמת שראינו, נניח $\displaystyle f(1)=1$,‏ $\displaystyle f(2)=10$,‏ ו$\displaystyle f(3)=2$. ארבע האפשרויות שראינו מקודם יעלו כך: עלות ההובלה היא $\displaystyle f(1)+f(1)+f(1)=3$. עלות ההובלה היא $\displaystyle f(1)+f(2)=11$. עלות ההובלה היא $\displaystyle f(2)+f(1)=11$. עלות ההובלה היא $\displaystyle f(3)=2$.

אנא מצא אלגוריתם יעיל למציאת נקודות השבירה כך שסך העלויות (שבירה והובלה) נמוך ככל האפשר. כלומר, אנא כתוב אלגוריתם יעיל שימצא את העלות המינימלית וכן ידפיס את נקודות השבירה של עלות זו.