A Complete Combinatorial Solution for a Coins Change Puzzle and Its Computer Implementation

Daxin Zhu (Quanzhou Normal University)
Xiaodong Wang (Quanzhou Normal University)

Indonesian Journal of Electrical Engineering and Computer Science
Vol 12, No 8: August 2014

In this paper, we study a combinatorial problem encountered in monetary systems. The problem concerned is to find an optimal solution R(k; n) of a combinatorial problem for some positive integers k and n. To the authors' knowledge, there is no eficient solutions for this problem in the literatures so far. We first show how to find an eficient recursive construction algorithm based on the backtracking search strategy. Furthermore, we can give an explicit formula for finding the maximal elements of the solution. Our new techniques have improved the time complexities of the search algorithm dramatically.