Question

dynamic_programming
spring17_a

נתונים ערכי nn מטבעות c1,c2,,cnN{0}c_1,c_2,\ldots,c_n \in \mathbb{N} \setminus \{0\} וסכום כסף SN{0}S \in \mathbb{N} \cup \{0\}.

אנו רוצים להמיר את SS למטבעות על ידי שימוש בסוגי המטבעות הנתונים. בשאלה זו יש למצוא את המספר הקטן ביותר של מטבעות הנדרשים כדי להמיר את SS, או להודיע שאין המרה חוקית.

הציעו אלגוריתם שפותר את הבעיה בסיבוכיות זמן O(nS)O(nS). בניתוח הסיבוכיות נתחו גם את סיבוכיות הזיכרון.

1

Answers

Feedback