## 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.

Original language | English (US) |
---|---|

Pages (from-to) | 159-169 |

Number of pages | 11 |

Journal | Journal of Computer and System Sciences |

Volume | 124 |

DOIs | |

State | Published - Mar 2022 |

## Keywords

- Coin changing
- Dynamic programming
- Fine-grained complexity
- Frobenius problem
- Knapsack

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics