Change-making problem

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

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

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

Dynamic programming

Making a list of ways to make each amount from one upwards (an example of a dynamic programming method)

Linear programming

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

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

The "optimal denomination problem"[1] 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.