What are greedy algorithms?

Greedy algorithms are a type of algorithms that make a locally optimal choice at each step, hoping that this will lead to a globally optimal solution.

Key features:

• Local optimum: At each step, the solution that seems best at the moment is chosen, without considering future consequences.
• No backtracking: Decisions made cannot be revisited at later stages.
• Efficiency: Often simple to implement and have higher efficiency compared to more complex methods.

Examples of problems suitable for greedy algorithms:

• Change-making problem (coin change)
• Job scheduling problem (Interval Scheduling)
• Some minimum spanning tree problems (e.g., Prim's or Kruskal's algorithm)

Example of a greedy approach to the change-making problem (change of 100 rubles with coins of 50, 10, 5, 1):

1. Take the maximum possible number of 50 ruble coins (2 * 50 = 100).
2. Remainder: 0. Solution found.

Example where the greedy algorithm does not give an optimal solution (change of 82 rubles with coins of 50, 25, 10):

Greedy approach:

1. 1 * 50 = 50. Remainder: 32.
2. 1 * 25 = 25. Remainder: 7.
3. 0 * 10 = 0. Remainder: 7. Solution: 1 coin of 50 rubles, 1 coin of 25 rubles, 0 coins of 10 rubles (incomplete change)

Optimal approach:

1. 0 * 50 = 0. Remainder: 82.
2. 3 * 25 = 75. Remainder: 7.
3. 0 * 10 = 0. Remainder: 7. Solution: 3 coins of 25 rubles (incomplete change)

In this case, the optimal solution may exist, but the greedy algorithm does not find it.

Greedy algorithms work correctly only for greedy problems that possess the following properties:

• Optimal substructure property: The optimal solution of the problem contains optimal solutions of its subproblems.
• Greedy choice property: The locally optimal choice at each step leads to a globally optimal solution.

# Example of a greedy approach to the change-making problem
def greedy_change(amount, coins):
    result = {}
    sorted_coins = sorted(coins, reverse=True) # Sort coins in descending order
    remaining_amount = amount

    for coin in sorted_coins:
        count = remaining_amount // coin # How many coins of this denomination can be taken
        if count > 0:
            result[coin] = count
            remaining_amount -= count * coin # Reduce the remainder

    return result, remaining_amount

# Example usage
amount = 100
coins = [50, 10, 5, 1]
change, remaining = greedy_change(amount, coins)
print(f"For amount {amount} with coins {coins}: Change = {change}, Remainder = {remaining}")

amount_bad = 82
coins_bad = [50, 25, 10] # Example where greedy algorithm may not work
change_bad, remaining_bad = greedy_change(amount_bad, coins_bad)
print(f"For amount {amount_bad} with coins {coins_bad}: Change = {change_bad}, Remainder = {remaining_bad}")