Change-making problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The change-making problem addresses the following question: how can a given amount of money be made with the least number of coins of given denominations? It is a knapsack type problem, and has applications wider than just currency.

Mathematical definition[edit]

Given a set of integer coin values {w1, w2, ..., wn} where w1 = 1 and wj < wj+1 for 1 ≤ jn − 1, and a positive integer W, find a set of non-negative integers {x1, x2, ..., xn} which minimize

\sum_{j=1}^n x_j

subject to

\sum_{j=1}^n w_j x_j = W.

Non currency examples[edit]

An application of change-making problem can be found in computing the ways one can make a nine dart finish in a game of darts.

Methods of solving[edit]

Simple dynamic programming[edit]

A classic dynamic programming strategy works upward by finding the combinations of all smaller values that would sum to the current threshold. Thus, at each threshold, all previous thresholds are potentially considered to work upward to the goal amount W. For this reason, this dynamic programming approach may require a number of steps that is at least quadratic in the goal amount W.

Dynamic programming with the probabilistic convolution tree[edit]

The probabilistic convolution tree[1] can also be used as a more efficient dynamic programming approach. The probabilistic convolution tree merges pairs of coins to produce all amounts which can be created by that pair of coins (with neither coin present, only the first coin present, only the second coin present, and both coins present), and then subsequently merging pairs of these merged outcomes in the same manner. This process is repeated until the final two collections of outcomes are merged into one, leading to a balanced binary tree with W log(W) such merge operations. Furthermore, by discretizing the coin values, each of these merge operations can be performed via convolution, which can often be performed more efficiently with the fast Fourier transform (FFT). In this manner, the probabilistic convolution tree may be used to achieve a solution in sub-quadratic number of steps: each convolution can be performed in n log(n), and the initial (more numerous) merge operations use a smaller n, while the later (less numerous) operations require n on the order of W.

The probabilistic convolution tree-based dynamic programming method also efficiently solves the probabilistic generalization of the change-making problem, where uncertainty or fuzziness in the goal amount W makes it a discrete distribution rather than a fixed quantity, where the value of each coin is likewise permitted to be fuzzy (for instance, when an exchange rate is considered), and where different coins may be used with particular frequencies.

Linear programming[edit]

Integer Linear Programming is often a quick way to solve this kind of problem, but the time it will take to resolve the problem is not certain, and may be slow in some cases

Greedy method[edit]

In the US (and most other) coin systems, a greedy algorithm of picking the largest denomination of coin which is not greater than the remaining amount to be made will always produce the optimal result. This is not automatically the case, though: if the coin denominations were 1, 3 and 4, then to make 6, the greedy algorithm would choose three coins (4,1,1) whereas the optimal solution is two coins (3,3).

Related problems[edit]

The "optimal denomination problem"[2] is a problem for people who design entirely new currencies: What denominations should be chosen for the coins in order to minimize the average cost of making change—i.e., the average number of coins needed to make change? The version of this problem assumed that the people making change will use the minimum number of coins (from the denominations available). One variation of this problem assumes that the people making change will use the "greedy algorithm" for making change, even when that requires more than the minimum number of coins. Most current currencies use a 1-2-5 series, but some other set of denominations would require fewer denominations of coins or a smaller average number of coins to make change or both.

See also[edit]

References[edit]

  1. ^ Serang (2014): Serang, O. (2012). "The Probabilistic Convolution Tree: Efficient Exact Bayesian Inference for Faster LC-MS/MS Protein Inference". PLOS ONE 7 (3): e91507. doi:10.1371/journal.pone.0091507. 
  2. ^ J. Shallit. "What this country needs is an 18c piece". Mathematical Intelligencer 25 (2): 20–23. doi:10.1007/BF02984830.