Min-Coin Change

The Minimum Coin Change (or Min-Coin Change) is the problem of using the minimum number of coins to make change for a particular amount of cents, $n$ , using a given set of denominations $d_{1}\ldots d_{m}$ . This is closely related to the Coin Change problem.

Overview

The problem is typically asked as: If we want to make change for $N$ cents, and we have infinite supply of each of $S=\{S_{1},S_{2},\ldots ,S_{m}\}$ valued coins, what is the least amount of coins we need to make the change? (For simplicity's sake, the order does not matter.)

Mathematically, we are trying to minimize $\sum {x_{k}}$ for $N=\sum _{k=1\ldots m}{x_{k}S_{k}}$ where $x_{k}\geq 0,k\in \{1\ldots m\}$ Greedy Approach

There are special cases where the greedy algorithm is optimal - for example, the US coin system. However this is not true in the general case. An example of a counterexample is:

Given the denominations 1, 5, 10, 20, 25, and wish to make change for 40 cents, the greedy algorithm would give us 25, 10, 5, but the best solution only requires 2 coins - 2 of the 20 cent coins.

Recursive Formulation

$C(N,m)=\min {(C(N,m-1),C(N-S_{m},m)+1)}$ with the base cases:

• $C(N,m)=0,N=0$ • $C(N,m)=\infty ,N<0$ • $C(N,m)=\infty ,N\geq 1,m\leq 0$ If the result of $C(N,m)$ is either $0$ or $\infty$ then it is impossible make change for $N$ with the given coins.