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

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

נתונות $k$ מידות, $(n_1,m_1),...,(n_k,m_k)$, שלהן מותאמים מחירים $p_1,...,p_k$. כלומר:

1. חתיכת בד במידה $(n_1,m_1)$ שווה $p_1$ שקלים.
2. חתיכת בד במידה $(n_2,m_2)$ שווה $p_2$ שקלים.
3. ...
4. חתיכת בד במידה $(n_k,m_k)$ שווה $p_k$ שקלים.חוץ מ$k$ מידות אלה, כל המידות האחרות חסרות ביקוש, ולכן כל חתיכת בד במידה שונה

ממידות אלה שווה 0 שקלים. הנח שכל $n_i$ ו$m_i$ הוא מספר שלם חיובי ממש.

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

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

הנח שקיימת פונקציה תבנית:קוד בשורה המחזירה בזמן $O(1)$:

1. 0 אם $(i,j)$ אינה אחת מ$k$ המידות בעלות התועלת.
2. $p_k$ אם $(i,j)=(n_k,m_k)$.