אימות ופתרון מופע Subset Sum

שימוש נכון באורך קלט בינרי והוכחת נוסחת תכנות דינמי.

שאלה

למספרים חיוביים $a_1,\ldots,a_m,T$, נגדיר $D(i,t)$ כאמת אם תת־קבוצה של $i$ המספרים הראשונים מסתכמת ל-$t$. גזרו נוסחה, פתרו את $\{3,5,6,11\},T=14$, והסבירו מדוע האלגוריתם פסאודו־פולינומיאלי.

רמז 1

פתרון אינו כולל את $a_i$, או כולל אותו ונעזר בסכום קודם $t-a_i$.

רמז 2

בטבלה עמודה לכל מספר עד $T$, בעוד שלקידוד בינרי של $T$ נדרשים רק $\Theta(\log T)$ ביטים.

פתרון מלא

מאתחלים $D(0,0)=\text{true}$ ו-$D(0,t)=\text{false}$ עבור $t>0$. לכל $i\ge1$,

שני המקרים מחלקים בדיוק את תתי־הקבוצות לפי השאלה אם הן כוללות את $a_i$, ולכן הנכונות נובעת באינדוקציה.

במופע הנתון $3+5+6=14$, ולכן $D(4,14)$ אמת, ושחזור נותן את $\{3,5,6\}$.

בטבלה $(m+1)(T+1)$ תאים וזמן המילוי $O(mT)$. זה פולינומיאלי בערך המספרי $T$, אך $T$ עלול להיות מעריכי באורך הקידוד הבינרי שלו. לכן אין בכך הוכחה ש-SUBSET-SUM הבינרית ב-P. השייכות ל-NP נובעת בנפרד מתעודת ביטים וחיבור בינרי פולינומיאלי.

נקודת בדיקה

״פסאודו־פולינומיאלי״ מתאר תלות בערכים המקודדים; אין פירושו זמן מעריכי בכל מופע.

הערת מקור

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

טעויות נפוצות

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

מקורות ואימות

• 2026 transcript 15
• Garey-Johnson, SP13
• הערת כיסוי הקורפוס: אין כיסוי ישיר בסיכום הממוזג.
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

פתיחה בגלריית ההמחשות: תכנות דינמי ל־Subset Sum