Change-Making Problem

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms


Probabilistic Convolution Tree	2014	$O(n \log n)$	$O(n \log n)$
Dynamic Programming	1953	$O(Sn)$	$O(Sn)$
Brute Force	1940	$O(S^n)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms