Coin change problem (CCP)

Catalogue of combinatorial problems · Miscellaneous problems · Catalogue (PDF)

Definition 1: Coin change problem

Given:

1. a vector \(w \in \Z_{\ge 1}^n\) of \(n\) denominations, each available in unlimited supply,

2. an integer amount of change \(c \in \Z_{\ge 0}\) to return,

the Coin Change Problem (CCP) asks to decide how many coins of each denomination to use so that their total value is exactly equal to \(c\), and the total number of coins used is minimized. If no combination of coins returns exactly \(c\), the instance is infeasible.

What the course does on this problem

Technique	Where
Definition	This page
Dynamic programming	Ch. 16 «Principles of dynamic programming»; Ch. 27 «DP for the coin change problem»
Exercises	Ch. 27 (5 exercises)