Chan, Timothy M. ;
He, Qizheng
More on ChangeMaking and Related Problems
Abstract
Given a set of n integervalued coin types and a target value t, the wellknown changemaking 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 alltargets 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 alltargets problem in O(nt) time. Recently, Chan and He (SOSA'20) described a number of O(t polylog t)time algorithms for the original (singletarget) version of the changemaking problem, but not the alltargets version.
In this paper, we obtain a number of new results on changemaking and related problems:
 We present a new algorithm for the alltargets changemaking problem with running time Õ(t^{4/3}), improving a previous Õ(t^{3/2})time algorithm.
 We present a very simple Õ(u²+t)time algorithm for the alltargets changemaking 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 allcapacities version of the unbounded knapsack problem (for integer item weights bounded by u).
 For the original (singletarget) coin changing problem, we describe a simple modification of one of Chan and He’s algorithms that runs in Õ(u) time (instead of Õ(t)).
 For the original (singlecapacity) unbounded knapsack problem, we describe a simple algorithm that runs in Õ(nu) time, improving previous nearu²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 changemaking (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 ChangeMaking and Related Problems}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {29:129:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12895},
URN = {urn:nbn:de:0030drops128958},
doi = {10.4230/LIPIcs.ESA.2020.29},
annote = {Keywords: Coin changing, knapsack, dynamic programming, Frobenius problem, finegrained complexity}
}
26.08.2020
Keywords: 

Coin changing, knapsack, dynamic programming, Frobenius problem, finegrained complexity 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 