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.

[martasoricetti]

[tommasobattisti]

l_coins = [2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01]

def coinTest(coinList, change, expected):
    result = coinChange(coinList, change)
    if result == expected:
        return True
    else:
        return False

def coinChange(coinList, change):
    result = {}
    for coin in coinList:
        while round(change, 2) >= round(coin, 2):
            change = round(change, 2) - round(coin, 2)
            if coin not in result:
                result[coin] = 0
            result[coin] += 1
    return result

print(coinTest(l_coins, 3.78, {2: 1, 1: 1, 0.5: 1, 0.2: 1, 0.05: 1, 0.02: 1, 0.01: 1}))
print(coinTest(l_coins, 3, {2:1, 1: 1}))
print(coinTest(l_coins, 0, {}))
print(coinTest(l_coins, 872.61, {2: 436, 0.5: 1, 0.1: 1, 0.01: 1}))

[Postitisnt]

I checked the solution to understand why my algorithm was not returning the right solution. I was missing the float_diff function, I wasn't able to understand the reason why, for example, if I assign to a variable a float value, and then I check if such variable is equal to the value, it returned false. ex.

a = 0.33
print(a == 0.33)
~out
False

If I understand well, the reason is connected to the automatic approximation in python, am I right? In the code you can find as a comment what I was trying to implement instead of the float_diff function.

def co(change):
    coins = [2,1,0.5,0.2,0.05,0.02,0.01]
    result = dict()   
    for coin in coins:
        while coin <= change:
            if coin not in result:
                result[coin] = 0
            result[coin] += 1
            change = float_diff(change, coin) #change -= coin
    return result

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

def coTest(change, expected):
    result = co(change)
    if expected == result:
        return True
    else:
        return False

print(coTest(3.75, {2: 1, 1: 1, 0.5: 1, 0.2: 1, 0.05: 1}))
print(coTest(0, {}))
print(coTest(2, {2: 1}))
print(coTest(4, {2: 2}))

[MaddaGh]

values=[2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01]
def test_coins(values, change, expected):
    result = coins(values, change)
    if expected==result:
        return True
    else:
        return False

def coins(values, change):
    tmp=0
    result={}
    for coin in values:
        result[coin]= 0
        while tmp+coin <= change:
            result[coin]+=1
            tmp +=coin

    return result

print(test_coins(values, 4.52, {2: 2, 1: 0, 0.5: 1, 0.2: 0, 0.1: 0, 0.05: 0, 0.02: 1, 0.01: 0}))
print(test_coins(values, 177.26, {2: 88, 1: 1, 0.5: 0, 0.2: 1, 0.1: 0, 0.05: 1, 0.02: 0, 0.01: 1}))
print(test_coins(values, 0.83, {2: 0, 1: 0, 0.5: 1, 0.2: 1, 0.1: 1, 0.05: 0, 0.02: 1, 0.01: 1}))