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

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

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