Question

spring_9_b

dynamic_programming

יהיו $\{a_1, \ldots, a_n\}$ קבוצה של מספרים טבעיים.

א. הצע אלגוריתם המחשב את הקבוצה

\left\{ \sum_{i \in I} a_i \right\}_{I \subseteq [n]}

כלומר, על האלגוריתם לחשב את קבוצת כל אותם מספרים הניתנים להצגה כסכום של חלק מאיברי הסדרה. כך למשל עבור הקלט $\{1,2,5\}$ הפלט הוא $\{0,1,2,3,5,6,7,8\}$ (0 עבור $I = \emptyset$ ).

על האלגוריתם לרוץ בזמן $O\left(n\displaystyle{\sum_{i = 1}^n}a_i\right)$ . הוכיחו נכונות ונתחו סיבוכיות.

ב. הציעו אלגוריתם המכריע האם קיימת קבוצה $I \subseteq [n]$ כך ש-

\sum_{i \in I}a_i = \sum_{j \in [n] \setminus I}a_j

הוכיחו נכונות ונתחו סיבוכיות.

Answers

א. נסמן ב- $A_i = \{a_i, \ldots, a_n\}$ וב- $S_i$ את קבוצת המספרים שניתן להביע כסכום של תת קבוצה של $A_i$ .

נשים לב שמתקיים $S_i = S_{i + 1} \cup \{s + a_i\}_{s \in S_{i + 1}}$ , וכן $S_n = \{0, a_n\}$ .

אנחנו מעוניינים לחשב את $S_1$ וניתן לעשות זאת בטבלה בגודל $n \times \sum_{i = 1}^n a_i$ בזמן לינארי בגודל הטבלה.

ב. נשים לב שהטענה מתקיימת אם ורק אם קיימת תת קבוצה של איברים שסכומם $\frac{\sum_{a \in A}a}{2}$ , ולכן ניתן להפעיל את האלגוריתם של סעיף א' ולבדוק אם הערך $\frac{\sum_{a \in A}a}{2}$ נמצא ב- $S_1$ . אין שינוי בסיבוכיות מסעיף א'.