Greedy Algorithm

A classic example of a greedy algorithm is the “Coin Change Problem.” In this problem, you are given a set of coin denominations and a target amount to make change for. The goal is to find the minimum number of coins needed to make up that target amount.

Here’s a Python program that demonstrates the greedy approach for the Coin Change Problem:

def greedy_coin_change(coins, target_amount):
    # Sort the coins in descending order (greedy choice: use the largest coins first)
    # Initialize variables
    coin_count = 0
    remaining_amount = target_amount
    # Iterate through the sorted coins
    for coin in coins:
        while remaining_amount >= coin:
            # Use as many of the current coin as possible
            remaining_amount -= coin
            coin_count += 1
    if remaining_amount == 0:
        return coin_count
        return -1  # Change cannot be made with the given coins

# Example usage:
coins = [25, 10, 5, 1]
target_amount = 63
min_coins = greedy_coin_change(coins, target_amount)
if min_coins != -1:
    print(f"Minimum number of coins needed: {min_coins}")
    print("Change cannot be made with the given coins.")


We start by sorting the coin denominations in descending order because the greedy choice here is to use the largest available coins first.

We initialize two variables: coin_count to keep track of the number of coins used, and remaining_amount to keep track of the amount we still need to make change for.

We iterate through the sorted coins. In each iteration, we repeatedly use as many of the current coin as possible while it doesn’t exceed the remaining_amount.

If, after processing all the coins, remaining_amount becomes zero, we return the coin_count as the minimum number of coins needed to make change for the target amount. Otherwise, if remaining_amount is not zero, it means that we couldn’t make exact change with the given coins, so we return -1 to indicate this.

In the provided example, the program will output “Minimum number of coins needed: 6,” which means you need six coins (two quarters, one dime, and three pennies) to make change for 63 cents using the given coin denominations.

Pegicorn Technologies

Leave a Reply

Your email address will not be published. Required fields are marked *