Back to Search
Start Over
More on change-making and related problems.
- Source :
-
Journal of Computer & System Sciences . Mar2022, Vol. 124, p159-169. 11p. - Publication Year :
- 2022
-
Abstract
- Given a set of n integer-valued coin types and a target value t , the well-known change-making problem asks for the minimum number of coins that sum to t , assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j , for every j = 0 , ... , t. We obtain a number of new results on these problems, including (i) an algorithm for the all-targets problem with running time O ˜ (t 4 / 3) (improving a previous O ˜ (t 3 / 2) -time algorithm), (ii) a very simple O ˜ (u 2 + t) -time algorithm for the all-targets problem, where u denotes the maximum coin value, and (iii) an algorithm for the original (single-target) problem with running time O ˜ (u) (improving a previous O ˜ (t) -time algorithm by Chan and He (SOSA'20)). We also describe applications to the (single-capacity) unbounded knapsack problem and the minimum word break problem. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*KNAPSACK problems
*COINS
*DYNAMIC programming
*APPROXIMATION algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 124
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 153707982
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.09.005