Statements (27)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
algorithmic problem
|
| gptkbp:application |
cryptography
finance resource allocation |
| gptkbp:category |
combinatorial optimization
dynamic programming |
| gptkbp:complexity |
pseudo-polynomial time
|
| gptkbp:describes |
The Coin Change Problem asks for the number of ways to make change for a given amount using a set of coin denominations.
A variant asks for the minimum number of coins needed to make a given amount. |
| gptkbp:field |
gptkb:mathematics
computer science |
| gptkbp:firstKnownSolution |
early 20th century
|
| https://www.w3.org/2000/01/rdf-schema#label |
Coin Change Problem
|
| gptkbp:input |
set of coin denominations
target amount |
| gptkbp:NP-complete |
no
|
| gptkbp:output |
minimum number of coins
number of ways to make change |
| gptkbp:relatedTo |
gptkb:knapsack_problem
gptkb:integer_partition_problem subset sum problem |
| gptkbp:supportsAlgorithm |
dynamic programming
greedy algorithm |
| gptkbp:usedIn |
competitive programming
algorithm design courses |
| gptkbp:bfsParent |
gptkb:Dynamic_Programming
|
| gptkbp:bfsLayer |
6
|