In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 30th
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #07 exercise sheet]
In this problem you should submit a function as described. Inside the function do not print anything that was not asked!
Peter Pescadero, a frugal kid who loves saving money, is trying to pay an exact amount using the least number of coins possible. Given a set of coin denominations and a target amount, Peter wants to find the minimum number of coins needed to make that exact amount. Can you help him?
Write a function minimum_coins(coins, k) that given coins, an integer set of coin denominations and k, a positive amount, returns the minimum amount of coins that you need to use to make quantity k. In case the quantity is not achievable with the coins you have, return -1. You may assume you have an infinite supply of all coins.
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ |coins| ≤ 50 | number of coin denominations | |
| 1 ≤ k ≤ 10 000 | quantity to consider |
NOTE: an inneficient solution will most likely have Time Limit Exceeded.
This is a challenge exercise and is substantially harder than the other and might need algorithmic topics we have not yet spoken on the class.
| Example Function Calls | Example Output |
print(minimum_coins({1,5,7}, 11))
print(minimum_coins({1,5,10}, 10))
print(minimum_coins({3,6}, 10))
print(minimum_coins({1}, 42))
|
3 1 -1 42 |
Explanation of sample input: