Question

dynamic_programming

במדינת ארצות-הבריל ישנם nn סוגי מטבעות c1,,cnc_1,\ldots,c_n. ערכו של המטבע cic_i הוא wiw_i דולצ'ים. לקוחה ובידה שטר שערכו KK דולצ'ים נכנסת לסניף בנק ומבקשת מפקיד הבנק לפרוט את השטר למספר מינימלי אל מטבעות.

הציעו אלגוריתם שפותר את הבעיה.

1

Answers

הנחה: כל הערכים שלמים, KK פולינומי בגודל הקלט.

נסמן ב-f(i,k)f(i, k) את מספר המטבעות המינימלי שדרוש על מנת להגיע לסכום kk באמצעות המטבעות ci,,cnc_i, \dots, c_n. נשים לב שמתקיימת נוסחת הנסיגה הבאה:

f(i,k)=min{1+f(i,kci)f(i+1,k) f(i, k) = \min \begin{cases} 1 + f(i, k - c_i) \\ f(i + 1, k) \end{cases}

ובנוסף f(n+1,k)=f(n + 1, k) = \infty, f(i,0)=0f(i, 0) = 0, f(i,k<0)=f(i, k < 0) = \infty.

אנחנו מעוניינים למצוא את הערך f(1,K)f(1, K) וניתן לחשב אותו בטבלה בגודל n×Kn \times K.

סיבוכיות: נשים לב שחישוב ערך בודד לוקח O(1)O(1) זמן ובסך הכל O(nK)O(nK).

1
Feedback