Monedas

# Checks if the value is feasible with the candidate
def isFeasible(value, cand):
    return ((value//cand) != 0)

# Checks if the has reached a solution value
def isNotSol(value):
    return (value > 0)

# Greedy algorithm to solve the problem
def greedyCoins(value, cand, sol):
    # Current best candidate
    best = 0
    
    # Loop until the value reaches the desired value for the solution
    while isNotSol(value):
        # The current best candidate provides a feasible solution
        if (isFeasible(value, cand[best])):
            sol[best] += 1
            value -= cand[best]
        # The current best candidate does not provide a feasible solution, moves to the next best candidate
        else:
            best += 1
            
    return sol




########################################################

if __name__ == "__main__":
    cand = [500, 200, 100, 50, 20, 10, 5, 2, 1]
    value = 437
    sol = [0] * len(cand)
    
    greedyCoins(value, cand, sol)
    print(list(zip(sol, cand)))