0/1 Knapsack Problem

Q: איך מוצאים אילו פריטים נבחרו בבעיית התרמיל 0/1?

שמרו את הטבלה המלאה וחזרו לאחור מ־ best[n][capacity] . אם best[i][c] שונה מ־ best[i-1][c] , הפריט i-1 נארז, לכן רשמו אותו והפחיתו את המשקל שלו מ־ c . אחרת, עברו לשורה i-1 עם אותו c .

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

+10

יש לך n פריטים. משקל פריט i הוא weights[i] והערך שלו הוא values[i]. התרמיל שלך יכול לשאת משקל כולל של עד capacity. כל פריט קיים פעם אחת, ועליך לארוז אותו בשלמותו או להשאיר אותו מאחור. החזר את הערך הכולל המרבי שאפשר לארוז.

פונקציה

knapsack(weights: integer-array, values: integer-array, capacity: integer) → integer

weightsinteger-array: המשקל של כל פריט
valuesinteger-array: הערך של כל פריט
capacityinteger: המשקל המרבי שהתיק יכול לשאת
מחזירהinteger: הערך הכולל הגדול ביותר של פריטים שמשקליהם נכנסים בקיבולת

אילוצים

1 ≤ n ≤ 100, כאשר n = weights.length = values.length
1 ≤ weights[i] ≤ 1000
1 ≤ values[i] ≤ 10⁴
1 ≤ capacity ≤ 1000

דוגמאות

קלט: weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
פלט: 17
הסבר: פריטים 0 ו-2 שוקלים 4 + 3 = 7 ושווים 10 + 7 = 17. אריזת הפריט בעל הערך הגבוה ביותר תחילה (משקל 5, ערך 12) משאירה מקום רק לפריט 1, ובסך הכול 16.

שאלת המשך

נניח שהקיבולת יכולה להגיע ל־10^9, בעוד שסכום הערכים הוא לכל היותר 10^4. לפי מה היית מאנדקס את הטבלה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

שום סדר חמדני לא עובד: אריזת הפריט בעל הערך הגבוה ביותר ראשון נותנת 16, ולא 17, בדוגמה הראשונה. הערך הטוב ביותר מפריט i והלאה תלוי רק ב־i ובמקום שנותר, שהוא מספר שלם עד 1000. תא אחד בטבלה לכל זוג נותן O(n × capacity), ומספיקה שורה אחת אם עוברים על הקיבולות בסדר יורד.

נסה את שתי האפשרויות עבור כל פריט

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

האינטואיציה

נסמן את best(i, room) בתור ערך הפריטים המרבי שהפריטים החל מ־i יכולים להוסיף כשיש room יחידות פנויות; אחרי הפריט האחרון הערך הוא 0. דילוג על הפריט i נותן best(i+1, room). אריזתו, כאשר weights[i] ≤ room, נותנת values[i] + best(i+1, room-weights[i]). נשמור את הערך הגדול יותר. כל אריזה שמתאימה היא רצף אחד של בחירות אריזה ודילוג, והרקורסיה מנסה את כולן.

כל פריט מכפיל את מספר המסלולים. כשכל 100 הפריטים מתאימים יחד, כמו במקרה של משקל 10 לכל פריט בתיק שקיבולתו 1000, יש 2^100 מסלולים.

אלגוריתם

כתוב את best(i, room); החזר 0 כאשר i נמצא אחרי הפריט האחרון.
הגדר את skip לערך best(i+1, room).
אם weights[i] > room, החזר את skip.
אחרת, החזר את הגדול מבין skip לבין values[i] + best(i+1, room-weights[i]).
החזר את best(0, capacity).

def knapsack(weights, values, capacity):
    n = len(weights)

    # The most value items i, i+1, ... can add with room units of weight left
    def best(i, room):
        if i == n:
            return 0
        skip = best(i + 1, room)
        if weights[i] > room:
            return skip
        take = values[i] + best(i + 1, room - weights[i])
        return max(skip, take)

    return best(0, capacity)

מלאו טבלה לפי פריט וקיבולת

האינטואיציה

הרקורסיה מגיעה לאותו זוג (i, room) דרך מסלולים רבים. יש לכל היותר 101 × 1001, כלומר בערך 10^5, זוגות, לכן חשבו כל אחד מהם פעם אחת.

נסמן ב־best[i][c] את הערך המרבי שהפריטים הראשונים i יכולים להכניס לתיק בקיבולת c; שורה 0 כולה מכילה 0. עבור הפריט i-1 שמשקלו w וערכו v, השארתו בחוץ נותנת best[i-1][c], והכנסתו לתיק, כאשר w ≤ c, נותנת best[i-1][c-w] + v. שורה i קוראת רק את שורה i-1, לכן כל פריט נכנס לתא לכל היותר פעם אחת.

בדוגמה הראשונה, פריט 2 (משקל 3, ערך 7) מעלה את הקיבולת 7 ל־best[2][4] + 7 = 17. פריט 3 מציע לאחר מכן רק best[3][2] + 12 = 16, ולכן התשובה נשארת 17.

אלגוריתם

צרו טבלה עם n+1 שורות ו־capacity+1 עמודות, שכולן מכילות 0.
עבור כל שורה i מ־1 עד n, קחו את w = weights[i-1] ואת v = values[i-1].
עבור כל קיבולת c, הגדירו את best[i][c] להיות best[i-1][c].
אם w ≤ c וגם best[i-1][c-w] + v גדול יותר, שמרו את הערך הזה במקום.
החזירו את best[n][capacity].

def knapsack(weights, values, capacity):
    n = len(weights)
    # best[i][c]: the most value from the first i items within capacity c
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]  # leave item i-1 out
            if w <= c and best[i - 1][c - w] + v > best[i][c]:
                best[i][c] = best[i - 1][c - w] + v  # put it in
    return best[n][capacity]

שורה אחת, הקיבולות ירדו

האינטואיציה

השורה i זקוקה רק לשורה i-1, ולכן שומרים שורה אחת best[c] ודורסים אותה פריט אחר פריט. כיוון המעבר הוא שקובע אם התשובה נכונה.

במעבר כלפי מעלה על c, ייתכן ש-best[c-w] כבר יכלול את הפריט הנוכחי. פריט אחד במשקל 3 ובערך 5, עם קיבולת 6, נותן ערך 5 לקיבולת 3, ואז קיבולת 6 קוראת את הערך הזה והופכת ל-10: שני עותקים. במעבר כלפי מטה מ-capacity עד w, התא שקוראים נמצא מתחת לתא שכותבים אליו, והוא יידרס מאוחר יותר, כך שהוא עדיין מכיל את הערך מהשורה הקודמת.

המעבר כלפי מעלה הוא הלולאה הנכונה כאשר אפשר לקבל עותקים בלתי מוגבלים של הפריטים. כאן זמן הריצה נשאר O(n × capacity), והזיכרון מצטמצם לשורה אחת.

אלגוריתם

צרו את best עם capacity + 1 איברים, שכולם 0.
עבור כל פריט עם משקל w וערך v, עברו על c מ-capacity ועד w, בסדר יורד.
אם best[c-w] + v גדול מ-best[c], שמרו אותו ב-best[c].
החזירו את best[capacity].

def knapsack(weights, values, capacity):
    # best[c]: the most value from the items seen so far within capacity c
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Walk the capacities downward so each item goes in at most once
        for c in range(capacity, w - 1, -1):
            if best[c - w] + v > best[c]:
                best[c] = best[c - w] + v
    return best[capacity]

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

מעבר על הקיבולות בסדר עולה בגרסה עם שורה אחת אורז את אותו פריט פעמיים: פריט אחד במשקל 3 ובערך 5 בתיק שקיבולתו 6 מניב 10 במקום 5.
שורה של capacity רשומות במקום capacity + 1. החזרת best[capacity-1] גורמת לאובדן של כל אריזה שממלאת את התיק בדיוק, כמו פריט במשקל 1 בתיק שקיבולתו 1.
אתחול הרשומות למינוס אינסוף. התיק לא חייב להיות מלא, ולכן כל הרשומות מתחילות ב-0; עם מינוס אינסוף, הדוגמה השלישית מחזירה מינוס אינסוף במקום 0.
יש לדלג על פריט שמשקלו גדול מקיבולת התיק. בדוגמה השלישית, טווח סגור w...capacity עוצר את התוכנית ב-Swift, ו-(w+1):(capacity+1) סופר לאחור ב-R.

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

מהי סיבוכיות הזמן של בעיית התרמיל 0/1?

הטבלה פועלת בזמן O(n × capacity), בערך 10^5 צעדים עבור 100 פריטים וקיבולת של 1000, והגרסה עם שורה אחת משתמשת בזיכרון של O(capacity). החסם הוא פסאודו־פולינומי: הוא גדל בהתאם לערך הקיבולת, ולא למספר הספרות שלה. הבעיה הכללית היא NP-hard.

למה אלגוריתם חמדני לא עובד עבור בעיית התרמיל 0/1?

כלל חמדני לעולם אינו חוזר בו מבחירה, גם כאשר הפריט משאיר מקום ששום דבר אינו ממלא. בקיבולת 7, הפריט שמשקלו 5 וערכו 10 נמצא בתיקו על היחס הטוב ביותר, ובכל זאת הפריטים שמשקליהם 4 ו־3 שווים יחד 13. בחירה חמדנית לפי היחס היא אופטימלית רק בבעיית התרמיל השברית, שבה אפשר לחתוך פריטים.

איך מוצאים אילו פריטים נבחרו בבעיית התרמיל 0/1?

שמרו את הטבלה המלאה וחזרו לאחור מ־best[n][capacity]. אם best[i][c] שונה מ־best[i-1][c], הפריט i-1 נארז, לכן רשמו אותו והפחיתו את המשקל שלו מ־c. אחרת, עברו לשורה i-1 עם אותו c.

def knapsack(weights, values, capacity):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

weights = [4, 2, 3, 5]
values = [10, 4, 7, 12]
capacity = 7

הפלט הצפוי

0/1 Knapsack Problem

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסה את שתי האפשרויות עבור כל פריט

מלאו טבלה לפי פריט וקיבולת

שורה אחת, הקיבולות ירדו

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

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

בעיות דומות