Analiza

Uočimo da ćemo za fiksno $k$ i skup $\{1 \cdot 10^k, 2 \cdot 10^k, 5 \cdot 10^k\}$ u optimalnom rešenju iskoristiti:

• najviše jednu novčanicu tipa $1 \cdot 10^k$ (dve $1 \cdot 10^k$ se mogu zameniti jednom $2 \cdot 10^k$);
• najviše jednu novčanicu tipa $5 \cdot 10^k$ (dve $5 \cdot 10^k$ se mogu zameniti jednom $1 \cdot 10^{k+1}$);
• najviše dve novčanice tipa $2 \cdot 10^k$ (tri $2 \cdot 10^k$ se mogu zameniti jednom $1 \cdot 10^k$ i jednom $5 \cdot 10^k$), a ako iskoristimo barem dve tada ne koristimo $1 \cdot 10^k$ (dve $2 \cdot 10^k$ i jedna $1 \cdot 10^k$ se mogu zameniti jednom $5 \cdot 10^k$).

Odavde sledi da u optimalnom rešenju nema prenosa, tj. ako predstavimo $V=c_n 10^n + c_{n-1} 10^{n-1} + \dots + c_0 10^0$, novčanice tipa $d \cdot 10^k$ koristimo samo kako bismo se rešili člana $c_k 10^k$. Dakle, optimalno rešenje dobijamo prolaskom kroz $V$ cifru-po-cifru i sabiranjem minimalnog broja novčanica tipa $d \cdot 10^k$ čiji je zbir $c_k \cdot 10^k$. Na primer, za $c_k=7$ biramo skup $\{$$5 \cdot 10^{k}$, $2 \cdot 10^{k}$$\}$ što dodaje $2$ na konačan rezultat. Sve vrednosti minimalnog broja novčanica za $c_k \in \{0,\dots9\}$ se lako mogu izračunati: $[0, 1, 1, 2, 2, 1, 2, 2, 3, 3]$.

Ovaj zadatak je specijalan slučaj change making problema. Za skup novčanica dat u ovom zadatku, greedy pristup (ponovljeno biranje najvrednije novčanice koja nema vrednost veću od preostale sume) dao bi optimalno rešenje, ekvivalentno gore opisanom. Ipak, ovaj pristup nije optimalan za sve skupove novčanica, pa se ovaj problem u opštem slučaju rešava metodom dinamičkog programiranja.