Question

dynamic_programming

יהא dd מספר טבעי, ויהיו k ו-x1,,xnx_1,\ldots,x_n איברים ב-ZdZ_d. הצע אלגוריתם המחשב בכמה אופנים ניתן להכניס סימנים של חיבור וחיסור בין ה-x-ים, כך שתוצאת הביטוי המתקבל תהיה kk (כל החישובים מתבצעים מודולו dd).

כך למשל, אם ה-x-ים הם 7,6,97,6,9 ו-k=2k=2 אז עבור Z10Z_{10} האלגוריתם יחזיר 2 כי

7+6+92mod107+694mod1076+90mod107692mod10 \begin{array}{l} 7 + 6 + 9 \equiv 2 \mod 10 \\ 7 + 6 - 9 \equiv 4 \mod 10 \\ 7 - 6 + 9 \equiv 0 \mod 10 \\ 7 - 6 - 9 \equiv 2 \mod 10 \end{array}

על האלגוריתם לרוץ בסיבוכיות זמן של O(nd)O(nd) ובסיבוכיות מקום של O(d)O(d).

1

Answers

נסמן ב-fd(i,κ)f_d(i, \kappa) את מספר האופנים שניתן לשים סימני חיבור וחיסור בין האיברים xi,,xnx_i, \dots, x_n כך שתוצאת הביטוי המתקבל היא κ\kappa מודולו dd.

נשים לב שמתקיימת נוסחת הנסיגה הבאה:

fd(i,κ)=fd(i+1,κaimodd)+fd(i+1,aiκmodd) f_d(i, \kappa) = f_d(i + 1, \kappa - a_i \mod d) + f_d(i + 1, a_i - \kappa \mod d)

ושאנחנו מעוניינים בערך fd(1,k)f_d(1, k).

ניתן לחשב אתfd(1,k)f_d(1, k) בעזרת תכנון דינמי בטבלה בגודל n×dn \times d בסיבוכיות זמן של O(nd)O(nd). כדי לשפר את סיבוכיות המקום נשים לב שכל שורה בטבלה תלויה רק בשורה שאחריה ולכן מספיק לנו לזכור רק את השורה האחרונה שחישבנו בכל שלב.

1
Feedback