Min-Coin Change

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) = 1,N = 0
• C(N,m) = 0,N < 0
• $C( N, m ) = 0, N \geq 1, m \leq 0$