Lecture "Greedy algorithms", exercise 1

[essepuntato]

Implement the algorithm introduced in Section "Greedy algorithms" for returning the minimum amount of coins for a change. Accompany the implementation of the function with the appropriate test cases.

[sntcristian]

def test_do_coins(amount, expected):
    result = do_coins(amount)
    if expected == result:
        return True
    else:
        return False

def do_coins(amount):
    coins = [2.0, 1.0, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
    result = []
    return recursive_do_coins(amount, coins, result)

def recursive_do_coins(amount, coins, result):
    if amount == 0 or len(coins) == 0:
        return result
    else:
        curr_coin = coins[0]
        while curr_coin <= amount:
            result.append(curr_coin)
            amount = float_diff(amount, curr_coin)
        coins.remove(curr_coin)
        return recursive_do_coins(amount, coins, result)


def float_diff(f1, f2):
    return round(f1 - f2, 2)
    
print(test_do_coins(5.00, [2.0, 2.0, 1.0]))
print(test_do_coins(2.76, [2.0, 0.5, 0.2, 0.05, 0.01]))
print(test_do_coins(0.00, []))