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

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

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

הגדרת הבעיה

נתונים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} עצמים ולכל עצם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} נתונים מחירו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} ומשקלו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_i} . לכל עצם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} נסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} את מספר העצמים מהחפץ שנכניס לתרמיל. המטרה היא למקסם את הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^n p_ix_i} (המחיר הכולל של העצמים בתרמיל) בכפוף לאילוץ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^n w_ix_i \leq W} (משקלם הכולל של החפצים אינו עולה על החסם).

הגרסה הנפוצה והפשוטה ביותר היא בעיית תרמיל הגב הבינארי: בבעיה זו לכל חפץ יש עותק אחד בלבד ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i \in \{0,1\}} (כלומר, אם חפץ מסוים נכנס לתרמיל אזי יש רק אחד מסוגו בתרמיל).

בבעיית תרמיל הגב החסומה, לכל עצם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} יש כמות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_i} ומותר להכניס לתרמיל מספר עותקים של העצם: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i \in \{0,1,...,c_i\}} .

בבעיית תרמיל הגב הלא חסומה, מותר לקחת מספר עותקים בלתי מוגבל מכל עצם: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i \geq 0} .

NP-שלמות

גרסת ההכרעה של בעיית תרמיל הגב היא: בהינתן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} עצמים עם מחירים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} ומשקלים $w_{i}$ , ובהינתן מחיר כולל $P$ וחסם על המשקל W יש להכריע האם קיימת בחירה של העצמים כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^n p_ix_i \geq P} תחת האילוץ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^n w_ix_i \leq W} . בעיה זו היא NP-שלמה:

הוכחה שהבעיה ב-NP מתבצעת על ידי ההבחנה שבהינתן פתרון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} ניתן לוודא בזמן פולינומי האם מתקיימים התנאים $\sum _{i=1}^{n}p_{i}x_{i}\geq P$ ו- $\sum _{i=1}^{n}w_{i}x_{i}\leq W$ .
הוכחה שהבעיה היא NP-קשה מתבצעת על ידי רדוקציה מבעיית החלוקה^[3]^[4]: בהינתן מופע של בעיית החלוקה $a_{1},a_{2},...,a_{n}$ נוכל להגדיר מופע של בעיית תרמיל הגב שבו לכל $i$ מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_i=p_i=a_i} וכמו כן מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle W=P=\frac{\sum_{i=1}^n a_i}{2}} . קיים תרמיל חוקי^[5] עבור מופע הבעיה אם ורק אם קיימת חלוקה של העצמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = {a_1,a_2,...,a_n}} לשתי קבוצות בעלות סכום זהה: בהינתן חלוקה $A=X\cup Y$ התרמיל החוקי יהיה פשוט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} (נשים לב שמשקל התרמיל ומחירו הם בדיוק מחצית מסכום איברי $A$ ), ובהינתן תרמיל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} החלוקה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} תהיה לקבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X, A/X} (שוב, מטעמי חוקיות הפתרון, סכום כל קבוצה הוא מחצית סכום איברי $A$ ).

גישות לפתרון

תכנון דינאמי

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

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

בהינתן מופע של הבעיה כמתואר בחלק "הגדרת הבעיה", נגדיר $m[i,w]$ להיות מחיר הפתרון המיטבי שניתן להשיג באמצעות עצמים שמספר הסידורי שלהם אינו עולה על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} ושסכום משקלם אינו עולה על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} . הגדרה זו מאפשרת פיתוח נוסחת נסיגה ל- $m[i,w]$ :

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_i > w\,\!} אז מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m[i,\,w]=m[i-1,\,w]} (לא ניתן להשתמש בעצם שמספרו $i$ ).
אם $w_{i}\leq w$ אז מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+p_i)} (ניתן להשתמש בעצם שמספרו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} והמחיר המיטבי הוא המחיר המרבי מבין המקרה בו הערך נבחר והמקרה בו הוא לא נבחר).
תנאי הבסיס ייקבע להיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m[0,w]=0} לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} (ללא עצמים המחיר הכולל הוא תמיד 0).

כעת ניתן, באמצעות חישוב ערכי הטבלה $m$ , לחשב ברקורסיה את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m[n,W]} , הלוא הוא המחיר המיטבי לבעיה.

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

def knapsack01_dp(items, limit):
    table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
 
    for j in xrange(1, len(items) + 1):
        item, wt, val = items[j-1]
        for w in xrange(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]:

נמיין את העצמים (שמשקלם אינו גדול מהחסם; עצם שמשקלו גדול מהחסם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} אינו רלוונטי לבעיה) לפי יחס המחיר-משקל שלהם $p_{i}/w_{i}$ . נוסיף לתרמיל, כל עוד זה אפשרי, את העצם הבא ברשימה הממוינת לפי יחס מחיר-משקל (מתחילים עם העצם בעל היחס הגבוה ביותר). נסמן ב- $j$ את מספר העצמים שהצלחנו להכניס בצורה זו, ולכן ניתן לתאר את המחיר של העצמים שהכנסנו על ידי: $\sum _{i=1}^{j}p_{i}$ . כעת נתבונן על המחיר של העצם ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j+1} : ‏הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{j+1}} . אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^j p_i > p_{j+1}} , נשאיר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} העצמים בתיק, ואם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^j p_i < p_{j+1}} , נוציא את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} העצמים מהתיק, ונכניס במקומם את העצם ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j+1} .

הוכחה שאלגוריתם זה נותן פתרון 2-קירוב: נסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} את הערך של הפתרון האופטימלי. נתבונן בבעיה דומה בה מותר לנו להכניס חלקי עצמים (נניח חצי עצם), ולא רק עצמים שלמים, ונסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} את הערך של הפתרון האופטימלי עבור בעיה זו. הפתרון האופטימלי עבור בעיה בה מותר להכניס חלקי עצמים, הוא גדול-שווה לפתרון האופטימלי של הבעיה המקורית בה ניתן להכניס רק עצמים שלמים (שכן כל פתרון עבור הבעיה המקורית, הוא גם פתרון אפשרי של הבעיה עם חלקי עצמים).

אם יכולנו להכניס לתרמיל חלקי עצמים, אזי ברור שהפתרון האופטימלי היה להכניס את j העצמים הראשונים, ולהכניס חלק מהעצם ה-j+1 שבדיוק ממלא את המשקל שניתן עוד להכניס לתרמיל (המשקל שניתן עוד להכניס לתרמיל לאחר הכנסת j העצמים הראשונים הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle W - \sum_{i=1}^j w_i} , ולכן החלק של העצם ה-j+1 שיוכנס לתרמיל הוא $x_{j+1}={\frac {W-\sum _{i=1}^{j}w_{i}}{w_{j+1}}}<1$ ). לכן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\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 } , ולענייננו מה שחשוב זה ש: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{j+1} p_i \geq m }

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

לכן, אם נחלק את הסכום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{j+1} p_i} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{j} p_i} ול-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{j+1}} , בהכרח לפחות אחד משני הביטויים הללו חייב להיות בעל מחיר של לפחות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{m}{2}} , כיוון שסכום המשקלים של שניהם חייב להיות גדול-שווה ל- $m$ .

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

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

הערות שוליים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

[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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]