The week's pick
Reseach Article
ASH CC Algo.: Coin Change Algorithm Optimization
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 178 - Number 15 |
| Year of Publication: 2019 |
| Authors: Ashar Mehmood |
10.5120/ijca2019918787
|
Ashar Mehmood . ASH CC Algo.: Coin Change Algorithm Optimization. International Journal of Computer Applications. 178, 15 ( May 2019), 1-9. DOI=10.5120/ijca2019918787
Abstract
The Coin Change problem is to represent a given amount V with fewest number of coins m. As a variation of knapsack problem, it is known to be NP-hard problem. Most of the time, Greedy alogrithm (time complexity O(m), space complexity O(1)), irrespective of real money system, doesn’t give optimal solution. Dynamic algorithm (time complexity O(mV), space complexity O(V)) gives optimal solution but is still expensive as amount V can be very large. In this paper, we have presented a suboptimal solution for the coin change problem which is much better than the greedy algorithm and has accuracy comparable to dynamic solution. Moreover, comparison of different algorithms has been stated in this paper. Proposed algorithm has a time complexity of O(m2f) and space complexity of O(1), where f is the maximum number of times a coin can be used to make amount V. It is, most of the time, more efficient as compared to dynamic algorithm and uses no memoization, this is a significant advantage over dynamic approach.
References
- Richard E. Bellman, “Dynamic Programming”, Princeton University Press Princeton, Dover Publications, NY, USA, 1957.
- Kevin Q. Brown, “Dynamic Programming in Computer Science”, Technical Report CMU-CS-79-106, pp. 1-3, 1979.
- Donald E. Knuth, “The Art of Computer Programming”, Addison-Wesley, US, ISBN: 0-201-03801-3, 1968.
- John J. Bartholdi, “The Knapsack Problem”, DOI 10.1007/978-0-387-73699-0_2, ISSN 0884-8289, 2008.
- S Needleman, C Wuncsch, “A general method applicable to the search for similarities in the amino acid sequences of two proteins”, Journal of Molecular Biology, 1970.
- Richard E. Bellman, “On a routing problem”, Quarterly Applied Mathematics, DOI: 10.1090/qam/102435, 1958.
- G. S. Lueker, “Two NP-complete Problems in Non-negative Integer Programming”, Comput. Sci. Lab. Univ. Princeton, 1975.
- J. W. Wright, “The Change-Making Problem”, J. Assoc. Comput. Mach., Vol. 22, Issue 1, pp. 125-128, NY, USA, 1975.
- Thomas H. Cormen, Charles Eric Leiserson, Ronald Linn Rivest, Clifford Stein, “Introduction to Algorithms”, Chapter 16, Greedy Algorithm, ISBN: 978-0-262-03384-8, 2001.
- Xuan Chai, “Canonical Coin System for Change-Making problems” in Ninth International Conference on Hybrid Intelligent Systems MOE- Microsoft Laboratory for Intelligent Computing and Intelligent Systems”, pp. 1-2, DOI: 10.1109/HIS.2009.103, 2009.
- Susanna S. Epp, “Discrete Mathematics with Applications (4 th ed.)”, p.427, ISBN-10: 0495391328, 2010.
- Edsger W. Dijkstra, “Recursive Programming”, Numerische Mathematik, Vol. 2, Issue 1, doi: 10.1007/BF01386232, New Jersey, USA, pp. 312-318, 1960.
- Elmirap, “Coin Change”, LeetCode, Retrieved August 10, 2018 from url: https://leetcode.com/articles/coin-change/#, May 2016.
- Eric W. Weisstein, “Exhaustive Search” MathWorld—A wolfram Web Resource, Retrieved August 13, 2018 from url:http://mathworld.wolfram.com/ExhaustiveSearch.htl.
- Christian Charras, Thierry Lecroq, “Brute Force algorithm”, Retrieved August 13, 2018 from url: http://www-igm.univ-mlv.fr/~lecroq/string/node3.html, 1997.
Index Terms
Keywords