More on change-making and related problems

Timothy M. Chan, Qizheng He

Research output: Contribution to journalArticlepeer-review

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˜(t4/3) (improving a previous O˜(t3/2)-time algorithm), (ii) a very simple O˜(u2+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 languageEnglish (US)
Pages (from-to)159-169
Number of pages11
JournalJournal of Computer and System Sciences
Volume124
DOIs
StatePublished - Mar 2022

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Applied Mathematics
  • General Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'More on change-making and related problems'. Together they form a unique fingerprint.

Cite this