minte9

LearnRemember / ALGORITHMS

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
"""