def give_change(amount, coins): Given the amount of money (expressed as an integer as the total number of kopecks of Poldavia, Ruritania, Montenegro or some other such vaguely Eastern European 0ictional country that Tintin and similar fellows would visit) and the list of available denominations of coins (similarly expressed as kopecks), create and return a list of coins that add up to the amount using the greedy approach where you use as many of the highest denomination coins when possible before moving on to the next lower denomination. The list of coin denominations is guaranteed to be given in descending sorted order, as should your returned result also be.
Exact change only
def give_change(amount, coins):Given the amount of money (expressed as an integer as the total number of kopecks of Poldavia, Ruritania, Montenegro or some other such vaguely Eastern European 0ictional country that Tintin and similar fellows would visit) and the list of available denominations of coins (similarly expressed as kopecks), create and return a list of coins that add up to the amount using the greedy approach where you use as many of the highest denomination coins when possible before moving on to the next lower denomination. The list of coin denominations is guaranteed to be given in descending sorted order, as should your returned result also be.
|
amount |
coins |
Expected result |
|
64 |
[50, 25, 10, 5, 1]
|
[50, 10, 1, 1, 1, 1]
|
|
123 |
[100, 25, 10, 5, 1]
|
[100, 10, 10, 1, 1, 1]
|
|
100 |
[42, 17, 11, 6, 1]
|
[42, 42, 11, 1, 1, 1, 1, 1]
|
This problem, along with its countless variations, is a computer science classic when modi0ied to minimize the total number of returned coins. The above greedy approach then no longer produces the optimal result for all possible coin denominations. For example, using simple coin denominations of [50, 30, 1] and the amount of sixty kopecks to be exchanged, the greedy solution [50, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ends up using eleven coins by its unfortunate 0irst choice that prevents it from using any of the 30-kopeck coins that would be handy here, seeing that the optimal solution [30, 30] needs only two such coins! A more advanced recursive
Step by step
Solved in 2 steps
