Question
יהיו קבוצה של מספרים טבעיים.
א. הצע אלגוריתם המחשב את הקבוצה
כלומר, על האלגוריתם לחשב את קבוצת כל אותם מספרים הניתנים להצגה כסכום של חלק מאיברי הסדרה. כך למשל עבור הקלט הפלט הוא (0 עבור ).
על האלגוריתם לרוץ בזמן . הוכיחו נכונות ונתחו סיבוכיות.
ב. הציעו אלגוריתם המכריע האם קיימת קבוצה כך ש-
הוכיחו נכונות ונתחו סיבוכיות.
Answers
א. נסמן ב- וב- את קבוצת המספרים שניתן להביע כסכום של תת קבוצה של .
נשים לב שמתקיים , וכן .
אנחנו מעוניינים לחשב את וניתן לעשות זאת בטבלה בגודל בזמן לינארי בגודל הטבלה.
ב. נשים לב שהטענה מתקיימת אם ורק אם קיימת תת קבוצה של איברים שסכומם , ולכן ניתן להפעיל את האלגוריתם של סעיף א' ולבדוק אם הערך נמצא ב-. אין שינוי בסיבוכיות מסעיף א'.