# Cashier Problem: a Greedy Algorithm and an optimal Solution

*Nicolae Giurgiteanu*

*Informatica Economica*, 2006, vol. X, issue 4, 29-33

**Abstract:**
We will remind briefly the cashier problem. A cashier has leeway a range of different fractional coins and has to pay a certain amount using the most reduced number of coins. If we mark the pay-desk monetary with P {p ,..., pn } 1 = , each pi having as denomination di and with A the final sum, the cashier must determine a coins subset { } m S q ,..., q 1 = of P, so that i m i id q A Î£==1. In order to solve this problem, there are several solutions consisting in greedy algorithms. Although there is an optimal solution, in the present article we will highlight a greedy algorithm and an optimal solution for this problem. The solution known at the time being use a lot of memory and, in addition, is difficult to justify, occurring the risk of misunderstanding by the reader. Our solution is simpler and uses little memory

**Keywords:** greedy algorithm; cashier problem; optimal solution (search for similar items in EconPapers)

**Date:** 2006

**References:** Add references at CitEc

**Citations:** Track citations by RSS feed

**Downloads:** (external link)

http://www.revistaie.ase.ro/content/40/giurgiteanu.pdf (application/pdf)

**Related works:**

This item may be available elsewhere in EconPapers: Search for items with the same title.

**Export reference:** BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text

**Persistent link:** https://EconPapers.repec.org/RePEc:aes:infoec:v:x:y:2006:i:4:p:29-33

Access Statistics for this article

Informatica Economica is currently edited by *Ion Ivan*

More articles in Informatica Economica from Academy of Economic Studies - Bucharest, Romania Contact information at EDIRC.

Bibliographic data for series maintained by Paul Pocatilu ().