Min-Coin Change

From Algorithmist
Jump to navigation Jump to search

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, , using a given set of denominations . This is closely related to the Coin Change problem.


The problem is typically asked as: If we want to make change for cents, and we have infinite supply of each of 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 for where

Greedy Approach[edit]

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[edit]

with the base cases:

If the result of is either or then it is impossible make change for with the given coins.