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

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

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

הגדרת הבעיה

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

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

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

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

NP-שלמות

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

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

גישות לפתרון

תכנון דינמי

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

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

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

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

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

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

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)^[7].

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

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

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

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

${\displaystyle \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}$,     ולענייננו מה שחשוב זה ש:   ${\displaystyle \sum _{i=1}^{j+1}p_{i}\geq m}$

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

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

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

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

הערות שוליים

1. Vazirani, Algorithms, 2006
2. David Pisinger, Algorithms for Knapsack Problems ,1995
3. בעיית החלוקה היא בעיית ההכרעה המוגדרת באופן הבא: בהינתן מולטי קבוצה של מספרים שלמים, האם ניתן לחלק אותה לשתי מולטי קבוצות כך שסכום כל אחת מהן שווה?
4. Anupam Gupta, 15-854: Approximations Algorithms - Dynamic Programming, 2005
5. פתרון חוקי לבעיה הוא פתרון המקיים את כל האילוצים של הבעיה
6. מקור לקוד התוכנית: http://rosettacode.org/wiki/Knapsack_problem/0-1
7. Katherine Lai,The Knapsack Problem and Fully Polynomial Time Approximation Schemes (FPTAS)2006
8. Alexander Souza, Combinatorial Algorithms - Lecture Notes, Winter Term 10/11, page 40, 2011