On the Change-Making Problem
Timothy M. Chan, Qizheng He · Society for Industrial and Applied Mathematics eBooks · 2019
Given a set of n non-negative integers representing a coin system, the change-making problem seeks the fewest number of coins that sum up to a given value t, where each type of coin can be used an unlimited number of times. This problem is a popular homework exercise in dynamic programming, where the textbook solution runs in O(nt) time. It is not hard to solve this problem in O(tpolylogt) time by using convolution. In this paper, we present a simple deterministic O(t log t log log t) time algorithm, and later improve the running time to O(t log t) by randomization.