What are greedy algorithms?

A greedy algorithm constructs a solution to a problem by making the locally optimal choice at each step in the hope that this choice will lead to a globally optimal solution. It does not "look ahead" or "look back," but makes a decision that seems best at the moment without considering the consequences. Examples:

• Change-making problem: Giving the minimum number of coins for a certain amount. The greedy algorithm chooses the largest coin that does not exceed the remaining amount.
• Dijkstra's algorithm: Finds the shortest paths from one vertex to all others in a graph with non-negative edge weights. At each step, it chooses the vertex with the smallest current distance.

Greedy algorithms do not always provide an optimal solution for all problems, but in many cases, they are simple to implement and efficient in time. To prove the optimality of a greedy algorithm, two properties are usually used:

1. Greedy choice property: A locally optimal choice made by the greedy algorithm can be part of an optimal solution.
2. Optimal substructure: An optimal solution to the problem contains optimal solutions to subproblems.

# Example of a greedy algorithm for the change-making problem
def find_change(amount, coins):
    # assumes coins are sorted in descending order
    change = []
    for coin in coins:
        while amount >= coin:
            change.append(coin)
            amount -= coin
    return change

# Example usage
# print(find_change(67, [25, 10, 5, 1])) # [25, 25, 10, 5, 1, 1]