Fractional Knapsack
יש לך n פריטים. ערכו של פריט i הוא values[i] ומשקלו weights[i]. התיק שלך יכול להכיל משקל כולל של לכל היותר capacity, ואתה יכול לקחת כל חלק מפריט: חלק מפריט i שמשקלו w שווה values[i] × w / weights[i].
כתוב פונקציה בשם fractionalKnapsack שמחזירה את הערך הכולל המרבי שהתיק יכול להכיל, כשהוא מעוגל כלפי מטה למספר שלם.
פונקציה
- valuesinteger-array
- הערך של כל פריט
- weightsinteger-array
- המשקל של כל פריט
- capacityinteger
- המשקל המרבי שהתיק יכול להכיל
- מחזירהinteger
- הערך הכולל הגדול ביותר שנכנס לתיק, בעיגול כלפי מטה
אילוצים
1 ≤ n ≤ 5000, כאשרn = values.length = weights.length1 ≤ values[i], weights[i] ≤ 1041 ≤ capacity ≤ 108
דוגמאות
- קלט
- values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
- פלט
- 151
- הסבר
- הפריטים שווים 5, 3, 6 ו־2.5 ליחידת משקל. פריטים 2 ו־0 נכנסים בשלמותם ושווים 70, ונשאר מקום ל־27. 27 היחידות מתוך 30 של פריט 1 מוסיפות 81, ובסך הכול 151.
- קלט
- values = [10, 7]weights = [4, 3]capacity = 5
- פלט
- 12
- הסבר
- פריט 0 שווה 2.5 ליחידה ופריט 1 שווה בערך 2.33, לכן פריט 0 נכנס בשלמותו ושווה 10. יחידה אחת מתוך 3 היחידות של פריט 1 מוסיפה
7 / 3, ו־12 ושליש מעוגל כלפי מטה ל־12.
- קלט
- values = [5, 8]weights = [2, 3]capacity = 100
- פלט
- 13
- הסבר
- שני הפריטים נכנסים ונשאר עוד מקום, אז לוקחים את הכול: 5 + 8 = 13.
שאלת המשך
האם אפשר למצוא את התשובה בזמן O(n), בלי למיין את כל הפריטים?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
אם היה בתיק מקום ליחידת משקל נוספת, מאיזה פריט היית לוקח את היחידה הזאת?
ליחידת משקל יש את הערך הרב ביותר כשהיא מגיעה מהפריט בעל הערך הגבוה ביותר ליחידת משקל. מלאו את התיק מהפריט הצפוף ביותר ואילך; רק את הפריט האחרון שבו תיגעו חותכים.
מיין את הפריטים מהצפופים ביותר לצפופים פחות, בהשוואה בין
values[a] × weights[b]לביןvalues[b] × weights[a]כדי שלא תצטרך לחלק לעולם. קח פריטים שלמים כל עוד הם נכנסים, ואז הוסףvalues[i] × room / weights[i]באמצעות חילוק שלם עבור הפריט שממלא את התיק.
פתרון
מכיוון שאפשר לחתוך פריטים, הבעיה היא חמדנית, בניגוד לבעיית התרמיל 0/1: כל יחידת משקל צריכה להגיע מהפריט שנותר בו הערך הגבוה ביותר ליחידת משקל. מיין לפי הצפיפות הזאת ומלא את התרמיל לפי הסדר. השווה צפיפויות באמצעות כפל צולב ועגל כלפי מטה רק את הפריט שאתה חותך, כך שאף פעם לא נשמר שבר.
בחרו את הפריט הצפוף ביותר בכל סבב
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
מלא את התיק מהפריט בעל הצפיפות הגבוהה ביותר ומטה: קח אותו בשלמותו אם הוא מתאים, אחרת קח את החלק שממלא את התיק ועצור. מצא את הפריט שלא נוצל ובעל הצפיפות הגבוהה ביותר על ידי סריקה של כולם והשוואה בין values[i] × weights[j] לבין values[j] × weights[i] במקום לחלק. כאשר המשקלים חיוביים, הבדיקה זהה, ושתי המכפלות נשארות לכל היותר 10^8.
בחירה בפריט הצפוף ביותר תחילה היא הטובה ביותר: אם יש בתיק משקל כלשהו מפריט פחות צפוף, בעוד שפריט צפוף יותר לא הוכנס לתיק במלואו, החלפת המשקל הזה בפריט הצפוף יותר לא יכולה להוריד את הערך. ממשיכים להחליף עד שמגיעים לתכולה שבה הפריטים נבחרו לפי סדר הצפיפות, מהגבוהה לנמוכה.
עד n סבבים, שבכל אחד מהם סורקים את הפריטים שלא נוצלו — בערך n²/2 = 12.5 מיליון השוואות עבור n = 5000.
אלגוריתם
- סמן כל פריט כלא בשימוש והגדר
room = capacityו-total = 0. - כל עוד יש מקום, סרוק את הפריטים שאינם בשימוש כדי למצוא את הפריט בעל הצפיפות הגבוהה ביותר, והשווה צפיפויות באמצעות כפל בהצלבה.
- אם לא נותרו פריטים, עצור. אחרת, סמן את הפריט הזה כבשימוש.
- אם הוא נכנס, הוסף את הערך שלו ל-
totalוהפחת את המשקל שלו מ-room. אם הוא לא נכנס, הוסף אתvalues[i] × room / weights[i]באמצעות חילוק שלם, ועצור. - החזר את
total.
def fractionalKnapsack(values, weights, capacity):
n = len(values)
used = [False] * n
total = 0
room = capacity
while room > 0:
best = -1
for i in range(n):
# i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
best = i
if best == -1:
break # every item is already in the bag
used[best] = True
if weights[best] <= room:
total += values[best]
room -= weights[best]
else:
total += values[best] * room // weights[best] # the part that fits, rounded down
room = 0
return totalמיון לפי ערך ליחידת משקל
האינטואיציה
הסריקה מוצאת שוב ושוב את הפריט בעל הצפיפות הגבוהה ביותר, אבל הסדר לעולם אינו משתנה בין הסבבים. מיין את הפריטים פעם אחת, מהצפוף ביותר תחילה, באמצעות אותה השוואה לאחר כפל צולב. פריטים בעלי צפיפות שווה יכולים להופיע בכל סדר, כי הם שווים בערכם ליחידת משקל.
קח פריטים שלמים כל עוד הם נכנסים. את הפריט הראשון שאינו נכנס חותכים בלבד: הוא מוסיף values[i] × room / weights[i], וחלוקה שלמה מעגלת את התוצאה כלפי מטה. כל מה שלפניו הוא מספר שלם, ולכן עיגול המונח היחיד הזה נותן את התשובה המדויקת. המיון עולה O(n log n) והמעבר על הפריטים עולה O(n).
אלגוריתם
- צור רשימה של האינדקסים של הפריטים ומיין אותה מהצפיפות הגבוהה לנמוכה באמצעות השוואה בכפל צולב.
- הגדר
room = capacityואתtotal = 0. - עבור כל פריט בסדר הזה, אם
weights[i] ≤ room, הוסף את הערך שלו והפחת את המשקל שלו מ־room. - אחרת, הוסף את
values[i] × room / weights[i]באמצעות חילוק שלם ועצור. - החזר את
total.
from functools import cmp_to_key
def fractionalKnapsack(values, weights, capacity):
# a goes before b when values[a] / weights[a] > values[b] / weights[b],
# tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
def denser_first(a, b):
return values[b] * weights[a] - values[a] * weights[b]
order = sorted(range(len(values)), key=cmp_to_key(denser_first))
total = 0
room = capacity
for i in order:
if weights[i] <= room:
total += values[i] # the whole item fits
room -= weights[i]
else:
total += values[i] * room // weights[i] # the part that fits, rounded down
break
return total
מלכודות ומקרי קצה
- מיון לפי ערך בלבד או לפי משקל בלבד. בדוגמה הראשונה, הפריט ששוויו 90 מדורג רק במקום השלישי לפי צפיפות; לקיחתו ראשון משאירה מקום למחצית מהפריט ששוויו 50, כך שמקבלים 115 במקום 151.
- חלוקה לפני כפל. כאשר הערך הוא 13, המשקל הוא 7 והמקום הפנוי הוא 3,
13 / 7 * 3בחשבון של מספרים שלמים נותן 3, ואילו13 * 3 / 7נותן את התוצאה הנכונה, 5. - ציפייה לכך שצריך לחתוך פריט בכל פעם. בדוגמה השלישית כל הפריטים נכנסים, והתשובה היא סכום כל הערכים, 13.
שאלות נפוצות3
מהי סיבוכיות הזמן של בעיית התרמיל השברי?
מיון הפריטים לפי ערך ליחידת משקל עולה O(n log n), והמילוי מתבצע במעבר אחד, ולכן הסיבוכיות הכוללת היא O(n log n) עם שימוש ב־O(n) זיכרון לשמירת הסדר. סריקה למציאת הפריט הצפוף ביותר בכל סבב עולה O(n²).
למה האלגוריתם החמדני עובד עבור בעיית התרמיל השברית, אך לא עבור בעיית התרמיל 0/1?
חיתוך מאפשר להחליף משקל של פריט פחות צפוף במשקל של פריט צפוף יותר. בלי חיתוך, פריט צפוף יכול להשאיר מקום שאף פריט אחר לא ימלא. עם ערכים 8, 11, 15, משקלים 2, 3, 4 וקיבולת 7, בחירה קודם בפריט הצפוף ביותר לוקחת את המשקלים 2 ו-4 ומניבה 23, בעוד שהמשקלים 3 ו-4 מניבים 26. גרסת 0/1 דורשת תכנות דינמי.
איך פותרים את בעיית התרמיל החלקי בלי להשתמש במספרים בנקודה צפה?
כאשר המשקלים חיוביים, a / b > c / d היא אותה בדיקה כמו a × d > c × b, לכן השוו בין הצפיפויות באמצעות כפל בהצלבה. הערך הטוב ביותר הוא מספר שלם ועוד שבר אחד, values[i] × room / weights[i] עבור הפריט שנחתך, ולכן חלוקה שלמה אחת נותנת בדיוק את התשובה המעוגלת כלפי מטה.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def fractionalKnapsack(values, weights, capacity):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
values = [40, 90, 30, 50] weights = [8, 30, 5, 20] capacity = 40
הפלט הצפוי
151