May 2017
Intermediate to advanced
310 pages
8h 5m
English
Content preview from Python Data Structures and Algorithms
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
Coin-counting problem
Let's examine a very simple use of this greedy technique. In some arbitrary country, we have the denominations 1 GHC, 5 GHC, and 8 GHC. Given an amount such as 12 GHC, we may want to find the least possible number of denominations needed to provide change. Using the greedy approach, we pick the largest value from our denomination to divide 12 GHC. We use 8 because it yields the best possible means by which we can reduce the amount 12 GHC into lower denominations.
The remainder, 4 GHC, cannot be divided by 5, so we try the 1 GHC denomination and realize that we can multiply it by 4 to obtain 4 GHC. At the end of the day, the least possible number of denominations to create 12 GHC is to get a one 8 GHC and four 1 GHC notes. ...