Cashier Problem: a Greedy Algorithm and an 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

Keywords

• greedy algorithm
• cashier problem
• optimal solution