Disseminating quality controlled scientific knowledge

Cashier Problem: a Greedy Algorithm and an optimal Solution

ADD TO MY LIST

Author(s): Nicolae GIURGITEANU

Journal: Informatica Economica Journal
ISSN 1453-1305

Volume: X;
Issue: 4;
Start page: 29;
Date: 2006;
VIEW PDF DOWNLOAD PDF Original page

Keywords: greedy algorithm | cashier problem | optimal solution

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