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

נתונה פיסת בד שמידותיה $\displaystyle (n,m)$ (כלומר ארכה $\displaystyle n$ מטר, ורחבה $\displaystyle m$ מטר). הנח ש$\displaystyle n$ ו$\displaystyle m$ מספרים שלמים.

נתונות $\displaystyle k$ מידות, $\displaystyle (n_{1},m_{1}),...,(n_{k},m_{k})$, שלהן מותאמים מחירים $\displaystyle p_{1},...,p_{k}$. כלומר:

1. חתיכת בד במידה $\displaystyle (n_{1},m_{1})$ שווה $\displaystyle p_{1}$ שקלים.
2. חתיכת בד במידה $\displaystyle (n_{2},m_{2})$ שווה $\displaystyle p_{2}$ שקלים.
3. ...
4. חתיכת בד במידה $\displaystyle (n_{k},m_{k})$ שווה $\displaystyle p_{k}$ שקלים.חוץ מ$\displaystyle k$ מידות אלה, כל המידות האחרות חסרות ביקוש, ולכן כל חתיכת בד במידה שונה

ממידות אלה שווה 0 שקלים. הנח שכל $\displaystyle n_{i}$ ו$\displaystyle m_{i}$ הוא מספר שלם חיובי ממש.

דוגמה: בתרשים הבא, A מראה פיסת בד במידות $\displaystyle (2,3)$, וB מראה שתי מידות בעלת ערך: העליונה בעלת המידות $\displaystyle (3,2)$, והתחתונה בעלת המידות $\displaystyle (1,2)$. נניח שהמידה העליונה שווה 35 שקל, והתחתונה שווה 2 שקלים. .

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

דוגמה: כיצד נוכל להשתמש בפיסת הבד מA שבדוגמה הקודמת? לו היינו יכולים לסובב אותה, היינו יכולים להפיק ממנה צורה ששווייה 35 שקל ללא גזירה אחת. עם זאת, עדיין יש סדרת גזירות שתפיק צורות בשווי 4 שקלים. בתרשים הבא: A מראה את החתך הראשון: נחתוך את הצורה אנכית בשורה 1, ונקבל את שתי הצורות בB. את הצורה העליונה בB נחתוך אנכית בטור הראשון, ונקבל את שלוש הצורות בC. את הצורה התחתונה בC נחתוך אנכית בטור 2, ונקבל את ארבע הצורות בD. כל אחת מהשורות בD מכילה כעת צורה אחת ששווייה 2 שקלים, ועוד צורה חסרת ערך. . יש עוד סדרות חיתוך שיניבו צורות בשווי 4 שקלים, אך אין סדרה שתניב יותר מכך.

בשאלה זו עליך למצוא אלגוריתם יעיל למציאת סדרת החיתוך הרווחית ביותר. אנא הוכח שהאלגוריתם שמצאת עובד בסיבוכיות $\displaystyle O(n\cdot m\cdot (n+m))$.

הנח שקיימת פונקציה Value(i, j) המחזירה בזמן $\displaystyle O(1)$:

1. 0 אם $\displaystyle (i,j)$ אינה אחת מ$\displaystyle k$ המידות בעלות התועלת.
2. $\displaystyle p_{k}$ אם $\displaystyle (i,j)=(n_{k},m_{k})$.

כדאי לדעת: אפשר לפתור את הבעיה בצורה הבאה. מכינים טבלה בגודל $\displaystyle m$ על $\displaystyle n$ ובתא ה- $\displaystyle (i,j)$ שמים את הרווח מחיתוך הבד לגודל $\displaystyle (i,j)$. רווח זה יהיה המקסימום מהרווחים אותם אפשר להשיג מחיתוך הבד לרוחב, מחיתוך הבד לאורך, וממכירת הבד כפי שהוא (כפי שמוחזר מהפונקציה Value(i, j)).