Change-Making Problem: Difference between revisions
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
Space Complexity Graph
Time-Space Tradeoff
