[go: up one dir, main page]

Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Lecture "Greedy algorithms", exercise 1 #35

Open
essepuntato opened this issue Dec 18, 2018 · 2 comments
Open

Lecture "Greedy algorithms", exercise 1 #35

essepuntato opened this issue Dec 18, 2018 · 2 comments
Labels
Exercise The exercises that are introduced in the lectures.

Comments

@essepuntato
Copy link
Contributor

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

@essepuntato essepuntato added the Exercise The exercises that are introduced in the lectures. label Dec 18, 2018
@hizclick
Copy link
hizclick commented Dec 20, 2018

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
Copy link
Contributor Author
essepuntato commented Dec 22, 2018

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Exercise The exercises that are introduced in the lectures.
Projects
None yet
Development

No branches or pull requests

2 participants