בעיית תרמיל הגב

בעיית תרמיל הגב (באנגלית: Knapsack problem) היא בעיית מיטוב קומבינטורית הנחקרת בתחום מדעי המחשב. בבעיה זו נתונה קבוצת עצמים שלכל אחד מהם משקל ומחיר, ובנוסף נתון חסם על המשקל. המטרה היא למצוא אוסף של העצמים הנתונים שסכום משקליהם אינו עולה על החסם הנתון, ומחירו מרבי.

הבעיה נחשבת לבעיה חשובה במדעי המחשב בגלל הערך התאורטי שלה (הבעיה היא NP-שלמה), ועקב השימושים שלה בתחומים כגון הקצאת משאבים וקריפטוגרפיה.

הגדרת הבעיה

נתונים $n$ עצמים ולכל עצם $i$ נתונים מחירו $p_{i}$ ומשקלו $w_{i}$. לכל עצם $i$ נסמן ב-$x_{i}$ את מספר העצמים מהחפץ שנכניס לתרמיל. המטרה היא למקסם את הביטוי $\sum _{i=1}^{n}p_{i}x_{i}$ (המחיר הכולל של העצמים בתרמיל) בכפוף לאילוץ $\sum _{i=1}^{n}w_{i}x_{i}\leq W$ (משקלם הכולל של החפצים אינו עולה על החסם).

הגרסה הנפוצה והפשוטה ביותר היא בעיית תרמיל הגב הבינארי: בבעיה זו לכל חפץ יש עותק אחד בלבד ולכן $x_{i}\in \{0,1\}$ (כלומר, אם חפץ מסוים נכנס לתרמיל אזי יש רק אחד מסוגו בתרמיל).

בבעיית תרמיל הגב החסומה, לכל עצם $i$ יש כמות $c_{i}$ ומותר להכניס לתרמיל מספר עותקים של העצם: $x_{i}\in \{0,1,...,c_{i}\}$.

בבעיית תרמיל הגב הלא חסומה, מותר לקחת מספר עותקים בלתי מוגבל מכל עצם: $x_{i}\geq 0$.

NP-שלמות

גרסת ההכרעה של בעיית תרמיל הגב היא: בהינתן $n$ עצמים עם מחירים $p_{i}$ ומשקלים $w_{i}$, ובהינתן מחיר כולל $P$ וחסם על המשקל W יש להכריע האם קיימת בחירה של העצמים כך ש- $\sum _{i=1}^{n}p_{i}x_{i}\geq P$ תחת האילוץ $\sum _{i=1}^{n}w_{i}x_{i}\leq W$. בעיה זו היא NP-שלמה:

• הוכחה שהבעיה ב-NP מתבצעת על ידי ההבחנה שבהינתן פתרון $x$ ניתן לוודא בזמן פולינומי האם מתקיימים התנאים $\sum _{i=1}^{n}p_{i}x_{i}\geq P$ ו-$\sum _{i=1}^{n}w_{i}x_{i}\leq W$.
• הוכחה שהבעיה היא NP-קשה מתבצעת על ידי רדוקציה מבעיית החלוקה: בהינתן מופע של בעיית החלוקה $a_{1},a_{2},...,a_{n}$ נוכל להגדיר מופע של בעיית תרמיל הגב שבו לכל $i$ מתקיים $w_{i}=p_{i}=a_{i}$ וכמו כן מתקיים $W=P={\frac {\sum _{i=1}^{n}a_{i}}{2}}$. קיים תרמיל חוקי עבור מופע הבעיה אם ורק אם קיימת חלוקה של העצמים $A={a_{1},a_{2},...,a_{n}}$ לשתי קבוצות בעלות סכום זהה: בהינתן חלוקה $A=X\cup Y$ התרמיל החוקי יהיה פשוט $X$ (נשים לב שמשקל התרמיל ומחירו הם בדיוק מחצית מסכום איברי $A$), ובהינתן תרמיל $X$ החלוקה של $A$ תהיה לקבוצות $X,A/X$ (שוב, מטעמי חוקיות הפתרון, סכום כל קבוצה הוא מחצית סכום איברי $A$).

גישות לפתרון

תכנון דינמי

כיוון שהבעיה היא NP-שלמה, לא ידועים אלגוריתמים פולינומיים אשר מוצאים פתרון מיטבי. עם זאת, בגרסת הבעיה בה מובטח שכל משקלי הפריטים הם מספרים שלמים, קיים אלגוריתם המבוסס על תכנון דינמי אשר פותר באופן מיטבי את הבעיה בסיבוכיות זמן פסאודו-פולינומית (אם משקלי הפריטים לא שלמים מספר תתי הבעיות עלול להיות מעריכי ביחס לקלט).

האלגוריתם הבא פותר את בעיית תרמיל הגב הבינארית בסיבוכיות זמן $O(nW)$.

בהינתן מופע של הבעיה כמתואר בחלק "הגדרת הבעיה", נגדיר $m[i,w]$ להיות מחיר הפתרון המיטבי שניתן להשיג באמצעות עצמים שמספר הסידורי שלהם אינו עולה על $i$ ושסכום משקלם אינו עולה על $w$. הגדרה זו מאפשרת פיתוח נוסחת נסיגה ל-$m[i,w]$:

• אם $w_{i}>w\,\!$ אז מתקיים $m[i,\,w]=m[i-1,\,w]$ (לא ניתן להשתמש בעצם שמספרו $i$).
• אם $w_{i}\leq w$ אז מתקיים $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+p_{i})$ (ניתן להשתמש בעצם שמספרו $i$ והמחיר המיטבי הוא המחיר המרבי מבין המקרה בו הערך נבחר והמקרה בו הוא לא נבחר).
• תנאי הבסיס ייקבע להיות $m[0,w]=0$ לכל $w$ (ללא עצמים המחיר הכולל הוא תמיד 0).

כעת ניתן, באמצעות חישוב ערכי הטבלה $m$, לחשב ברקורסיה את $m[n,W]$, הלוא הוא המחיר המיטבי לבעיה.

הקוד הבא בשפת Python מממש את האלגוריתם המתואר:

def knapsack01_dp(items, limit):
    table = [[0 for w in range(limit + 1)] for j in range(len(items) + 1)]
 
    for j in range(1, len(items) + 1):
        item, wt, val = items[j-1]
        for w in range(1, limit + 1):
            if wt > w:
                table[j][w] = table[j-1][w]
            else:
                table[j][w] = max(table[j-1][w],
                                  table[j-1][w-wt] + val)
 
    result = []
    w = limit
    for j in range(len(items), 0, -1):
        was_added = table[j][w] != table[j-1][w]
 
        if was_added:
            item, wt, val = items[j-1]
            result.append(items[j-1])
            w -= wt
 
    return result

אלגוריתמי קירוב

גישה אחרת לפתרון הבעיה היא שימוש באלגוריתמי קירוב. לבעיה זו קיימים מספר אלגוריתמי קירוב כולל סכמת קירוב פולינומית מלאה (FPTAS).

האלגוריתם החמדן הבא מוצא תרמיל שמחירו לכל הפחות מחצית המחיר של הפתרון המיטבי (2-קירוב):

נמיין את העצמים (שמשקלם אינו גדול מהחסם; עצם שמשקלו גדול מהחסם $W$ אינו רלוונטי לבעיה) לפי יחס המחיר-משקל שלהם $p_{i}/w_{i}$. נוסיף לתרמיל, כל עוד זה אפשרי, את העצם הבא ברשימה הממוינת לפי יחס מחיר-משקל (מתחילים עם העצם בעל היחס הגבוה ביותר). נסמן ב-$j$ את מספר העצמים שהצלחנו להכניס בצורה זו, ולכן ניתן לתאר את המחיר של העצמים שהכנסנו על ידי: $\sum _{i=1}^{j}p_{i}$. כעת נתבונן על המחיר של העצם ה-$j+1$: ‏$p_{j+1}$. אם $\sum _{i=1}^{j}p_{i}>p_{j+1}$, נשאיר את $j$ העצמים בתיק, ואם $\sum _{i=1}^{j}p_{i}<p_{j+1}$, נוציא את $j$ העצמים מהתיק, ונכניס במקומם את העצם ה-$j+1$.

הוכחה שאלגוריתם זה נותן פתרון 2-קירוב: נסמן ב-$m$ את הערך של הפתרון האופטימלי. נתבונן בבעיה דומה בה מותר לנו להכניס חלקי עצמים (נניח חצי עצם), ולא רק עצמים שלמים, ונסמן ב-$M$ את הערך של הפתרון האופטימלי עבור בעיה זו. הפתרון האופטימלי עבור בעיה בה מותר להכניס חלקי עצמים, הוא גדול-שווה לפתרון האופטימלי של הבעיה המקורית בה ניתן להכניס רק עצמים שלמים (שכן כל פתרון עבור הבעיה המקורית, הוא גם פתרון אפשרי של הבעיה עם חלקי עצמים).

אם יכולנו להכניס לתרמיל חלקי עצמים, אזי ברור שהפתרון האופטימלי היה להכניס את j העצמים הראשונים, ולהכניס חלק מהעצם ה-j+1 שבדיוק ממלא את המשקל שניתן עוד להכניס לתרמיל (המשקל שניתן עוד להכניס לתרמיל לאחר הכנסת j העצמים הראשונים הוא $W-\sum _{i=1}^{j}w_{i}$, ולכן החלק של העצם ה-j+1 שיוכנס לתרמיל הוא $x_{j+1}={\frac {W-\sum _{i=1}^{j}w_{i}}{w_{j+1}}}<1$). לכן:

$\sum _{i=1}^{j+1}p_{i}=\sum _{i=1}^{j}p_{i}+p_{j+1}\geq \sum _{i=1}^{j}p_{i}+x_{j+1}p_{j+1}=M\geq m$,     ולענייננו מה שחשוב זה ש:   $\sum _{i=1}^{j+1}p_{i}\geq m$

ובמילים: המחיר של העצמים 1 עד j+1 גדול מהמחיר של עצמים 1 עד j + המחיר של חלק מעצם j+1, ששווה ל-M (הפתרון של הבעיה עם חלקי עצמים), שגדול-שווה ל-m (הפתרון של הבעיה שלנו).

לכן, אם נחלק את הסכום $\sum _{i=1}^{j+1}p_{i}$ ל-$\sum _{i=1}^{j}p_{i}$ ול-$p_{j+1}$, בהכרח לפחות אחד משני הביטויים הללו חייב להיות בעל מחיר של לפחות ${\frac {m}{2}}$, כיוון שסכום המשקלים של שניהם חייב להיות גדול-שווה ל-$m$.

קישורים חיצוניים

• David Pisinger, Algorithms for Knapsack Problems, Ph.D thesis, February 1995, University of Copenhagen
• מימושים של בעיית תרמיל הגב הבינארית במגוון שפות תכנות