Change-making problem

The change-making problem addresses the following question: how can a given amount of money be made with the least number of coins of given denominations? It is a knapsack type problem, and has applications wider than just currency.

Coin values can be modeled by a set of n distinct positive integer values (whole numbers), arranged in increasing order as w₁ = 1 through w_n. The problem is: given an amount W, also a positive integer, to find a set of non-negative (positive or zero) integers {x₁, x₂, ..., x_n}, with each x_j representing how often the coin with value w_j is used, which minimize the total number of coins

subject to

An application of change-making problem can be found in computing the ways one can make a nine dart finish in a game of darts.

A classic dynamic programming strategy works upward by finding the combinations of all smaller values that would sum to the current threshold. Thus, at each threshold, all previous thresholds are potentially considered to work upward to the goal amount W. For this reason, this dynamic programming approach may require a number of steps that is at least quadratic in the goal amount W.

We can use dynamic programming strategy to solve this problem because it exhibits optimal substructure.

Proof.

Suppose ${\displaystyle S}$ is the optimal solution for making ${\displaystyle n}$ coins. Then ${\displaystyle S'=S-c}$, for some ${\displaystyle c\in S}$, is an optimal solution for the subproblem of making ${\displaystyle n-c}$ coins.

...
Wikipedia