Coin Change
Find the minimum number of coins needed to make the a coin change, using a set of coin denominations. Start with the largest denomination that is less than or equal to the target amount and continue with smaller denominations until you reach the target.
# Denominations list
D = [1, 5, 10, 25]
# Result list
R = []
# Target amount
target = 63
for n in reversed(D):
while n <= target - sum(R): # Look Here
R.append(n)
print(R, "Min number of coins:", len(R))
"""
[25, 25, 10, 1, 1, 1] Min number of coins: 6
"""
Variation
Find a combination of numbers from the set M to get as close as possible to the target value without exceeding it.
# Denominations list
M = [1, 2, 3, 5, 10, 20, 30, 50, 100, 130, 150]
# Result set (no duplicates)
R = set()
target = 322
for n in reversed(M):
if n <= target - sum(R):
R.add(n)
print(R, sum(R))
"""
[150, 130, 30, 10, 2, 0] 322
"""
Last update: 358 days ago