Question

spring_9_b
dynamic_programming

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

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

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

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

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

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

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

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

1

Answers

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

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

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

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

1
Feedback