Rod Cutting Problem

Q: מהי סיבוכיות הזמן של בעיית חיתוך המוט?

הטבלה דורשת זמן O(n²) וזיכרון O(n): האורך len מנסה len חתיכות ראשונות, ובסך הכול יש n(n+1)/2 ניסיונות. ללא תשובות שמורות, הרקורסיה מבצעת בדיוק 2^n קריאות עבור מוט באורך n, מכיוון שכל אורך קורא לכל האורכים הקצרים ממנו.

Q: למה חיתוך מוטות הוא בעיית תרמיל בלתי מוגבלת?

התייחסו לכל חתיכה באורך k כאל פריט שמשקלו k ושוויו prices[k-1] , עם מספר בלתי מוגבל של עותקים, ואל המוט כאל תיק בעל קיבולת n שיש למלא בדיוק. לכן, הערך הכולל הטוב ביותר של הפריטים הוא המחיר הטוב ביותר של המוט.

Q: איך מוצאים היכן לחתוך את המוט?

יש לשמור, עבור כל אורך, את החתיכה הראשונה k שהעניקה לו את המחיר הטוב ביותר. מתחילים באורך n: חותכים חתיכה באורך השמור, עוברים לאורך שנותר וחוזרים על הפעולה עד שמגיעים ל־0. החתיכות מרכיבות תוכנית מיטבית אחת.

בינוניתכנון דינמי

+10

יש לך מוט באורך n, כאשר n = prices.length. חתיכה באורך k נמכרת במחיר prices[k-1]. אפשר לחתוך את המוט לחתיכות באורכים שלמים, בכמות שרוצים, או למכור אותו כחתיכה אחת. החזר את הסכום המרבי שאפשר להרוויח ממכירת כולו.

פונקציה

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] הוא המחיר של חתיכה באורך k; אורך המוט הוא prices.length
מחזירהinteger: הסכום המרבי שהחכה כולה יכולה להרוויח

אילוצים

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

דוגמאות

קלט: prices = [2, 5, 7, 8]
פלט: 10
הסבר: שני חלקים באורך 2 נמכרים ב־5 + 5 = 10. מכירת המוט בשלמותו מניבה 8, וחלק באורך 1 יחד עם חלק באורך 3 מניבים 2 + 7 = 9.

שאלת המשך

מה אם מותר לך לחתוך את המוט לכל היותר m פעמים? מה כל תא בטבלה צריך לדעת במקרה כזה?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

למוט באורך n יש 2^(n-1) דרכים לחתוך אותו. אין צורך בכל הדרכים: יהיו אשר יהיו החלק הראשון והחלקים שנותרו, הם יוצרים מוט קצר יותר שמעלה את אותה שאלה. לכן יש רק n+1 תשובות, אחת לכל אורך, וחישובן מהקצר ביותר ועד הארוך ביותר דורש O(n²) צעדים.

נסה כל אורך עבור החלק הראשון

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

תהיה התוכנית אשר תהיה, לחתיכה שבקצה השמאלי יש אורך k בין 1 לאורך המוט, והיא מניבה prices[k-1]; יתרת התוכנית חותכת מוט באורך length-k. לכן best(length) הוא 0 כאשר האורך הוא 0, ואחרת הוא הערך הגדול ביותר של prices[k-1] + best(length-k) עבור כל k, כאשר k = length מוכר את המוט בשלמותו. לכל תוכנית יש חתיכה ראשונה, ולכן המקסימום הזה מכסה את כל התוכניות.

כל קריאה מסתעפת לכל האורכים הקצרים יותר, ולכן מספר הקריאות מוכפל בכל יחידת אורך: מוט באורך 40 יוצר בערך 2^40, או 10^12, קריאות.

אלגוריתם

כתבו את best(length), שמחזירה 0 עבור אורך 0.
עבור כל חתיכה ראשונה k מ-1 עד length, חשבו את prices[k-1] + best(length-k).
החזירו את הערך הגדול ביותר מבין הערכים האלה.
החזירו את best(n).

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

המחיר הטוב ביותר לכל אורך, מהקצר ביותר תחילה

האינטואיציה

הרקורסיה מחשבת מחדש את אותם ערכים: best(2) נדרש על ידי best(3), best(4) וכל מוט ארוך יותר. יש רק n+1 אורכים, לכן חשבו כל אחד מהם פעם אחת ושמרו אותו במערך best. אורך קורא רק אורכים קצרים ממנו, ולכן מילוי המערך מ-0 כלפי מעלה מבטיח שכל ערך יהיה מוכן כשקוראים אותו.

עבור [2, 5, 7, 8]: best[1] הוא 2, best[2] הוא הגדול מבין 2 + 2 ו-5, כלומר 5, best[3] הוא 7, ו-best[4] הוא הגדול מבין 2 + 7, 5 + 5, 7 + 2 ו-8, כלומר 10.

בניגוד לתרמיל 0/1, best[len-k] עשוי כבר להכיל חתיכות באורך k, וזה בדיוק מה שרוצים, מכיוון שאפשר לחתוך אורך כמה פעמים שרוצים. האורך len מנסה len חתיכות ראשונות: בסך הכול n(n+1)/2 צעדים, בערך 5 × 10^5 עבור מוט באורך 1000.

אלגוריתם

צרו את best עם n + 1 איברים, כולם 0.
עבור כל length מ-1 עד n, נסו כל חתיכה ראשונה k מ-1 עד length.
חשבו את prices[k-1] + best[length-k] ושמרו את הערך הגדול ביותר ב-best[length].
החזירו את best[n].

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

מלכודות ומקרי קצה

קריאה של prices[k] עבור אורך k. כך מתמחרים כל חתיכה כאילו הייתה ארוכה ביחידה אחת, וב-k = n עוברים את סוף המערך; יש להשתמש ב-prices[k-1].
השמטת k = length, החתיכה שלא חותכים. אז best[1] נשאר 0, ו-[1, 3, 8] מקבל ציון 3 במקום 8.
חיתוך חמדני לפי המחיר הטוב ביותר ליחידה. ב-[2, 7, 11, 13], אורך 3 מניב את המחיר הגבוה ביותר ליחידה, אבל 11 עבורו ועוד 2 עבור השארית נותנים 13, בעוד ששתי חתיכות באורך 2 נותנות 14.
ביצוע מִזכּוּר מלמעלה למטה ב-Python. הקריאות הרקורסיביות עדיין נערמות לעומק כאורך המוט: עבור מוט באורך 1000 נערמות 1001 קריאות, מעבר למגבלת ברירת המחדל של 1000. מלאו את המערך מלמטה למעלה.

שאלות נפוצות4

מהי סיבוכיות הזמן של בעיית חיתוך המוט?

הטבלה דורשת זמן O(n²) וזיכרון O(n): האורך len מנסה len חתיכות ראשונות, ובסך הכול יש n(n+1)/2 ניסיונות. ללא תשובות שמורות, הרקורסיה מבצעת בדיוק 2^n קריאות עבור מוט באורך n, מכיוון שכל אורך קורא לכל האורכים הקצרים ממנו.

למה חיתוך מוטות הוא בעיית תרמיל בלתי מוגבלת?

התייחסו לכל חתיכה באורך k כאל פריט שמשקלו k ושוויו prices[k-1], עם מספר בלתי מוגבל של עותקים, ואל המוט כאל תיק בעל קיבולת n שיש למלא בדיוק. לכן, הערך הכולל הטוב ביותר של הפריטים הוא המחיר הטוב ביותר של המוט.

איך מוצאים היכן לחתוך את המוט?

יש לשמור, עבור כל אורך, את החתיכה הראשונה k שהעניקה לו את המחיר הטוב ביותר. מתחילים באורך n: חותכים חתיכה באורך השמור, עוברים לאורך שנותר וחוזרים על הפעולה עד שמגיעים ל־0. החתיכות מרכיבות תוכנית מיטבית אחת.

איך הפתרון משתנה אם כל חיתוך עולה כסף?

מכירת המוט בשלמותו אינה דורשת חיתוך, בעוד שכל חתיכה ראשונה אחרת מוסיפה חיתוך אחד. לכן best[len] מקבל את הערך הגדול יותר מבין prices[len-1] לבין הערך הגדול ביותר של prices[k-1] + best[len-k] - cost עבור k שקטן מ-len. שאר הטבלה נשארת ללא שינוי.

def cutRod(prices):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

prices = [2, 5, 7, 8]

הפלט הצפוי