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
that sum to a target value . Formally, we seek to minimise
subject to: where
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
with the base case
Visual Representation
The following diagram illustrates the dynamic programming state transitions for
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.