בעיית הסכומים החלקיים

בעיית הסכום החלקי (Subset Sum Problem) שואלת: בהינתן קבוצה של מספרים שלמים, האם קיימת תת־קבוצה לא ריקה שסכום איבריה הוא אפס? לדוגמה, בקבוצה {-7, -3, -2, 8, 5} קיימת תת־קבוצה {-2, -3, 5} שסכומה אפס. בעיה זו היא NP-שלמה, כלומר קשה למצוא אלגוריתם שעובד בזמן פולינומי לכל קלט.

מקרה שקול הוא: בהינתן קבוצה I ומספר s, האם קיימת תת־קבוצה שסכומה s? מקרה מיוחד נוסף הוא בעיית החלוקה, שמבקשת לחלק את האיברים לשתי תת־קבוצות עם אותו סכום.

למרות הקושי התיאורי, קיימים מספר אלגוריתמים מעשיים או משופרים. הם נחלקים לאקספוננציאליים, לפסאודו־פולינומיים ולאלגוריתמי קירוב.

האלגוריתם הפשוט ביותר בודק את כל תתי־הקבוצות האפשריות. יש 2^n תתי־קבוצות, לכן זמן הריצה הגולמי הוא O(2^n · n).

קיים שיפור משמעותי שנקרא "meet‑in‑the‑middle" (הוצג על ידי הורוביץ וסהני, 1972). הרעיון: חלקו את הקבוצה לשני חלקים שווים. חשבו את כל הסכומים האפשריים בכל חלק. מיין את שתי הרשימות וחפש זוג סכומים שמתאימים יחד ליעד s. זמן הריצה יורד לכ־O(2^{n/2}) אך נדרש מקום גם כן O(2^{n/2}).

אלגוריתם פסאודו־פולינומי פועל בזמן פולינומי בערכי הקלט ולא במספר הביטים שדרושים לייצוגם. שימוש נפוץ הוא בתכנון דינמי. נסמן A כסכום השליליים ו‑B כסכום החיוביים. נגדיר Q(i,s) כבוליאנית שאומרת האם ניתן להשיג סכום s מתוך האיברים הראשונים עד i. הפתרון הוא Q(n,0).

מממשים טבלה בגודל בערך n × (B−A). בסיס: Q(1,s) נכון אם x1 שווה ל‑s. עבור i>1 משתמשים ברקורסיה: Q(i,s) נכון אם Q(i−1,s) נכון, או x_i שווה s, או Q(i−1,s−x_i) נכון. מילוי הטבלה לוקח זמן O(n·(B−A)).

השיטה מהירה כאשר הערכים קטנים, אבל אינה פולינומית בגודל הקלט שנמדד בביטים, ולכן היא נקראת פסאודו־פולינומית.

קיימת גם שיטה מקירוב (FPTAS) שמאפשרת ריצת זמן פולינומית ב‑n וב‑1/c, כאשר c>0 הוא פרמטר דיוק. הרעיון הבסיסי: בנו רשימה S שמכילה סכומים אפשריים, והוסיפו כל פעם סכומים חדשים מתוך איבר xi. אחרי איחוד הרשימות מסננים (trim) ערכים קרובים אחד לשני ומשאירים רק ערכים מייצגים כך שהרשימה נשארת בגודל מוגבל. בכל שלב מוסיפה הפעולה שגיאה קטנה ≤ c·s/n, ובסך הכל לאורך n שלבים השגיאה הכוללת היא ≤ c·s. כך מקבלים פתרון קרוב בזמן פולינומי ב‑n וב‑1/c.

בעיית הסכום החלקי שואלת: נתונה קבוצת מספרים. האם יש תת־קבוצה לא ריקה שסכומה הוא אפס? לדוגמה: בקבוצה {-7, -3, -2, 8, 5} יש את התת־קבוצה {-2, -3, 5} שסכומה הוא אפס.

הבעיה קשה למצוא לה פתרון מהיר לכל קלט. לכן משתמשים בכמה שיטות שונות.

שיטה פשוטה בודקת את כל תתי־הקבוצות. יש הרבה תתי־קבוצות, ולכן זה לוקח זמן רב. שיפור מהיר מחלק את הקבוצה לשני חלקים. מחשבים את כל הסכומים של כל חלק. אז מחפשים שני סכומים שמתאימים יחד.

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

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