Coin Problem

computation algorithms optimisation

Definition

Coin Problem

The coin problem (or change-making problem) asks for the minimum number of coins from a given set of denominations $D=\{d_1,d_2,\dots ,d_n\}$ that sum to a target value $V$.

Formally, we seek to minimise ${\sum }_{i=1}^n{x}_i$ subject to:

$$\sum \_{i=1}^n{x}_i{d}_i=V$$

where $x_i\ge 0$ are integers representing the count of each denomination.

Approaches

Greedy Algorithm

For many “canonical” coin systems (like the British Pound or US Dollar), a greedy algorithm—repeatedly taking the largest denomination that does not exceed the remaining value—yields an optimal solution. However, for arbitrary coin systems, the greedy approach may fail to find the minimum number of coins or fail to find a solution at all.

Dynamic Programming

The general version of the problem can be solved using dynamic programming. Let $C(v)$ be the minimum number of coins required to make change for value $v$:

$$C(v)=1+\min \_i:d_i\le v\{C(v-d_i)\}$$

with the base case $C(0)=0$.

Visual Representation

The following diagram illustrates the dynamic programming state transitions for $D=\{1,3,4\}$ and $V=6$:

Complexity

The problem is NP-hard in its general form, although the version where an infinite supply of coins is available (the “Change-making Problem”) is solvable in pseudo-polynomial time using dynamic programming.