File CoinChange.h

↰ Parent directory (ADS/optimization)

The change with the fewest coins (introduction of chapter 14): the greedy choice takes the largest coin that fits, and is optimal for coins of 50, 10, 5 and 1 cents, but not for coins of 11, 5 and 1, where it pays 15 with five coins instead of three of 5.

Definition (ADS/optimization/CoinChange.h)

Detailed Description

optimalChange() is the dynamic programming, the fewest coins N[ c ] of each amount c, :math:` N[ c ] = 1 + min_{d leq c} N[ c - d ] `, O( n C ).

The contracts [see File Contract.h]: the coins are positive and the amount is not negative; the change of greedyChange() sums to the amount, and optimalChange() uses at most c coins. The operations are defined in CoinChange.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 14, https://algoritmicamente.it/materiali/libro/capitoli/cap14.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions