Change-Making Problem: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 6: Line 6:
== Parameters ==  
== Parameters ==  


n: number of coin denominations
$n$: number of coin denominations


S: sum to be made
$S$: sum to be made


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 22: Line 22:
| [[Dynamic Programming (Change-Making Problem Change-Making Problem)|Dynamic Programming]] || 1953 || $O(Sn)$ || $O(Sn)$ || Exact || Deterministic || [https://dl.acm.org/doi/10.1145/321864.321874 Time]
| [[Dynamic Programming (Change-Making Problem Change-Making Problem)|Dynamic Programming]] || 1953 || $O(Sn)$ || $O(Sn)$ || Exact || Deterministic || [https://dl.acm.org/doi/10.1145/321864.321874 Time]
|-
|-
| [[Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem)|Probabilistic Convolution Tree]] || 2014 || $O(n log n)$ || $O(n log n)$ ||  || Deterministic || [https://www.ncbi.nlm.nih.gov/pubmed/24626234 Time] & [https://pubmed.ncbi.nlm.nih.gov/24626234/ Space]
| [[Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem)|Probabilistic Convolution Tree]] || 2014 || $O(n \log n)$ || $O(n log n)$ ||  || Deterministic || [https://www.ncbi.nlm.nih.gov/pubmed/24626234 Time] & [https://pubmed.ncbi.nlm.nih.gov/24626234/ Space]
|-
|-
|}
|}

Revision as of 08:24, 10 April 2023

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