More on change-making and related problems (Q2051861): Difference between revisions

This paper considers the change-making or coin-changing problem: given a set of \(n\) types of coins, each of integer value, the goal is to select the minimum number of coins whose total value is equal to a specified target value \(t\). This problem is known to be weakly NP-hard and the previously to this paper best known algorithm for it had time complexity \(O(t \log t \log \log t)\). The paper also considers the all-targets version of the problem, where the goal is to solve the change-making problem for all target values \(j\) between 1 and a specified upper bound \(t\). The previously to this paper best algorithm for the problem has time complexity \(\tilde O(t^{3/2})\), where as usual the \(\tilde O\) notation hides polylogarithmic factors. The paper gives a simple FFT-based algorithm for the all-targets version of the problem that has time complexity \(\tilde O(t^{4/3})\). The complexity of the problem is also studied with respect to the largest coin value \(u\), and an algorithm is given for the problem with time complexity \(O(u^2 \log u + t)\). This is a very simple 3-line algorithm that interestingly has a rather complex correctness proof using a theorem on the Frobenius problem. This algorithm can be modified to solve the all-capacities unbounded knapsack problem within the same time bound. The final results presented in the paper are \begin{itemize} \item an \(\tilde O((t \sigma)^{2/3}+t)\) algorithm for the all-targets change-making problem, where \(\sigma\) is the sum of values of the \(n\) coin types \item an \(\tilde O(u)\) algorithm for the change-making problem \item an \(\tilde O(nu)\) algorithm for the unbounded knapsack problem, and \item a proof that an algorithm of Bringmann et al. can solve the minimum word-break problem in time \(\tilde O(nm^{1/3}+m)\), where the minimum word-break problem consists in expressing a string \(s\) of length \(n\) as the concatenation of the smallest number of words from a set \(D\) of strings with total length \(m\). \end{itemize}