Lecture "Greedy algorithms", exercise 1

[essepuntato]

Implement the informal algorithm introduced in Section "Greedy algorithms" for returning the minimum amount of coins for a change.

[hizclick]

here is what this code does: it takes all coins as sorted input list, so the maximum coin is at index 0. Then it checks if the amount is included in the first index value if not it will pop it out from the list. If it is included then that coin will be inserted to the result list.

def test_change(amount,coins,expected):
    if expected == change(amount,coins):
        return True
    else:
        return False
def change(amount, coins, result=list()):
    if amount== 0:
        return result
    else:
        if len(coins)>0:
            maximum_coin = coins[0]
            if amount>= maximum_coin:
                result.append(maximum_coin)
                amount= round(amount- maximum_coin, 2)
                return change(amount,coins)
            else:
                if result:
                    coins.pop(0)
                    return change(amount,coins)
    return result
print(test_change(6.44,[2,1,0.5,0.2,0.1,0.05,0.02,0.01],[2,2,2,0.2,0.2,0.02,0.02]))

[essepuntato]

Hi all,

I'm posting here my take on the exercise - you can find the source of this online as usual.

# Test case for the algorithm
def test_return_change(amount, expected):
    result = return_change(amount)
    if expected == result:
        return True
    else:
        return False

# Code of the algorithm
def return_change(amount):
    result = {}
    coins = [2.0, 1.0, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]

    for coin in coins:
        while float_diff(amount, coin) >= 0:
            amount = float_diff(amount, coin)

            if coin not in result:
                result[coin] = 0
            result[coin] = result[coin] + 1

    return result

def float_diff(f1, f2):
    return round(f1 - f2, 2)

change = 2.76
print(test_return_change(5.00, {2.0: 2, 1.0: 1}))
print(test_return_change(2.76, {2.0: 1, 0.5: 1, 0.2:1, 0.05:1, 0.01: 1}))

Note that I've used an ancillay function I've developed called float_diff, so as to address one well-known issue of Python with floating numbers.