minte9

LearnRemember / ALGORITHMS

Coin Change

 
""" Coin change

Problem: Using a set of coins, 
find the mininum number of coins to make the change.

Algorithm: Start with the largest denominator that is less than or equal 
with the target ammount and continue with the smaller ones.
"""

D = [1, 5, 10, 25]
R = []

target = 63

for n in reversed(D):
    while n <= target - sum(R):  # Look Here
        R.append(n)

print(R, f"Mininum number of coins = {len(R)}")

"""
    [25, 25, 10, 1, 1, 1] Mininum 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.

 
""" Coin change (variation)

No duplicates allowed in the result (set).
"""

COINS = [1, 2, 3, 5, 10, 20, 30, 50, 100, 130, 150]

def coin_change(target):
    R = set()
    remaining = target - sum(R)

    for n in reversed(COINS):
        if n <= remaining:
            R.add(n)
            remaining = target - sum(R)
    return R

assert sum(coin_change(326)) == 326
print(coin_change(326))

"""
    {1, 130, 5, 10, 150, 30}
"""