Change-making problem

The change-making problem addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a special case of the integer knapsack problem, and has applications wider than just currency. It is also the most common variation of the coin change problem, a general case of partition in which, given the available denominations of an infinite set of coins, the objective is to find out the number of possible ways of making change for a specific amount of money, without considering the order of the coins. It is weakly NP-hard, but may be solved optimally in pseudo-polynomial time by dynamic programming.

Mathematical definition

Coin values can be modeled by a set of distinct positive integer values (whole numbers), arranged in increasing order as through . The problem is: given an amount , also a positive integer, to find a set of non-negative (positive or zero) integers , with each representing how often the coin with value is used, which minimize the total number of coins f(W)=\sum_{j=1}^n x_j subject to \sum_{j=1}^n w_j x_j = W.

Non-currency examples

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. Another application is computing the possible atomic (or isotopic) composition of a given mass/charge peak in mass spectrometry.

Methods of solving

Simple dynamic programming

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 requires a number of steps that is O(nW), where n is the number of types of coins. def _get_change_making_matrix(set_of_coins, r: int): m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)] for i in range(1, r + 1): m[0][i] = float("inf") # By default there is no way of making change return m def change_making(coins, n: int): """This function assumes that all coins are available infinitely. if coins are only to be used once, change m[c][r - coin] to m[c - 1][r - coin]. n is the number to obtain with the fewest coins. coins is a list or tuple with the available denominations. """ m = _get_change_making_matrix(coins, n) for c, coin in enumerate(coins, 1): for r in range(1, n + 1): # Just use the coin if coin == r: m[c][r] = 1 # coin cannot be included. # Use the previous solution for making r, # excluding coin elif coin > r: m[c][r] = m[c - 1][r] # coin can be used. # Decide which one of the following solutions is the best: # 1. Using the previous solution for making r (without using coin). # 2. Using the previous solution for making r - coin (without # using coin) plus this 1 extra coin. else: m[c][r] = min(m[c - 1][r], 1 + m[c][r - coin]) return m[-1][-1]

Greedy method

For many real-world coin systems, such as those used in the US and many other countries, a greedy algorithm of picking the largest denomination of coin which is not greater than the remaining amount to be made will produce the optimal result. This is not the case for arbitrary coin systems or even some real world systems, though. For instance, if we consider the old (now withdrawn) Indian coin denominations of 5, 10, 20 and 25 paise, then to make 40 paise, the greedy algorithm would choose three coins (25, 10, 5) whereas the optimal solution is two coins (20, 20). Another example is attempting to make 40 US cents without nickels (denomination 25, 10, 1) with similar result — the greedy chooses seven coins (25, 10, and 5 × 1), but the optimal is four (4 × 10). A coin system is called "canonical" if the greedy algorithm always solves its change-making problem optimally. It is possible to test whether a coin system is canonical in polynomial time.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369016980 under CC BY-SA 4.0; modifications have been made.

Names in other languages