Change-Making Problem (Change-Making Problem)

Description

Given an unlimited amount of coins of denominations $c_1, \ldots, c_n$, and a desired sum $S$, find the minimum number of coins necessary to make $S$.

Parameters

$n$: number of coin denominations

$S$: sum to be made

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Brute Force	1940	$O(S^n)$	$O(n)$	Exact	Deterministic
Dynamic Programming	1953	$O(Sn)$	$O(Sn)$	Exact	Deterministic	Time
Probabilistic Convolution Tree	2014	$O(n \log n)$	$O(n log n)$		Deterministic	Time & Space

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination