Za sustav novčanica
kažemo da je dobar ako "greedy" postupak vraćanja novca uvijek rezultira s najmanjim brojem isplaćenih novčanica. Dokažite da je sustav
dobar ako i samo ako postoji
takav da je
.
Napomena: U greedy postupku u svakom koraku vraćamo najviše moguće najvećih mogućih novčanica. Nadalje,
označava najmanji cijeli broj veći od (ili jednak)
.
![1 = n_1 < n_2, ... < n_k](/media/m/7/5/4/75406eed9c7b178c22566882e199f2be.png)
![1 < b < a](/media/m/5/7/5/575c5f31f84b3993d31b0afe1cb6304f.png)
![k \in \mathbb{N}](/media/m/3/7/4/3740df5f7c5224aee0c08404b0d63c46.png)
![\lceil\frac{a}{k}\rceil = b](/media/m/d/6/8/d68d5dd354d4b04a61d42ff0c3cb96dc.png)
Napomena: U greedy postupku u svakom koraku vraćamo najviše moguće najvećih mogućih novčanica. Nadalje,
![\lceil x\rceil](/media/m/e/5/5/e55d3cf23126e3a9283aa4ce0b473552.png)
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)