 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-128958
URL:

;

### More on Change-Making and Related Problems

 pdf-format:

### 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. For example, the textbook dynamic programming algorithms can solve the all-targets problem in O(nt) time. Recently, Chan and He (SOSA'20) described a number of O(t polylog t)-time algorithms for the original (single-target) version of the change-making problem, but not the all-targets version. In this paper, we obtain a number of new results on change-making and related problems: - We present a new algorithm for the all-targets change-making problem with running time Õ(t^{4/3}), improving a previous Õ(t^{3/2})-time algorithm. - We present a very simple Õ(u²+t)-time algorithm for the all-targets change-making problem, where u denotes the maximum coin value. The analysis of the algorithm uses a theorem of Erdős and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the all-capacities version of the unbounded knapsack problem (for integer item weights bounded by u). - For the original (single-target) coin changing problem, we describe a simple modification of one of Chan and He’s algorithms that runs in Õ(u) time (instead of Õ(t)). - For the original (single-capacity) unbounded knapsack problem, we describe a simple algorithm that runs in Õ(nu) time, improving previous near-u²-time algorithms. - We also observe how one of our ideas implies a new result on the minimum word break problem, an optimization version of a string problem studied by Bringmann et al. (FOCS'17), generalizing change-making (which corresponds to the unary special case).

### BibTeX - Entry

```@InProceedings{chan_et_al:LIPIcs:2020:12895,
author =	{Timothy M. Chan and Qizheng He},
title =	{{More on Change-Making and Related Problems}},
booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
pages =	{29:1--29:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-162-7},
ISSN =	{1868-8969},
year =	{2020},
volume =	{173},
editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 