Algorithm Introduction To Greedy Strategy Complete Guide

Introduction to Greedy Algorithms

Greedy algorithms are an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. This approach is often used in optimization problems where you want to find the best solution possible, such as maximizing profits or minimizing costs. The idea is to never look back and never reconsider the choices made once they are done.

Characteristics of Greedy Algorithms

1. Make the Locally Optimal Choice: At each step, make the choice that looks the best at that moment.
2. Build Up a Global Solution: Keep making locally optimal choices until you reach a global solution.

When to Use Greedy Algorithms

Greedy algorithms work well when it is possible to split the problem into multiple steps and the local decisions do not conflict with the overall goal and lead to the global solution.

Common problems solved using greedy algorithms include:

• Minimum Spanning Trees (e.g., Prim’s and Kruskal’s algorithms)
• Shortest Path Problems (e.g., Dijkstra’s algorithm)
• Activity Selection Problem
• KnapSack Problem (specifically, the fractional knapsack variant)

Example 1: Activity Selection Problem

The activity selection problem involves selecting the maximum number of non-overlapping activities from a list. Each activity has a start time and an end time.

Steps:

1. Sort all activities according to their finish time.
2. Select the first activity from the sorted array and mark it as selected.
3. For the remaining activities, do the following:
   • If the start time of this activity is greater than or equal to the finish time of the previous selected activity, then select this activity and mark it as selected.
4. Repeat until no more activities can be selected.

Example Code in Python:

def activity_selection(activities):
    # Sort activities based on finish time
    sorted_activities = sorted(activities, key=lambda x: x[1])
    
    # The first activity always gets selected
    last_selected = sorted_activities[0]
    print(f"Selected: {last_selected}")
    
    # Consider rest of the activities
    for i in range(1, len(sorted_activities)):
        activity = sorted_activities[i]
        if activity[0] >= last_selected[1]:
            print(f"Selected: {activity}")
            last_selected = activity

# Each tuple represents (start_time, end_time)
activities = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 7), (8, 9)]
activity_selection(activities)

Input:

• A list of activities represented as tuples of (start_time, end_time).

Output:

• Selected: (1, 3)
• Selected: (4, 6)
• Selected: (8, 9)

These are the activities the algorithm selects.

Example 2: Fractional KnapSack Problem

In the fractional knapsack problem, you are given a set of items with respective weights and values, along with a maximum weight capacity of a knapsack. You can break the items for maximal value.

Steps:

1. Calculate the value-to-weight ratio for each item.
2. Sort all items in decreasing order of value-to-weight ratio.
3. Initialize total value to 0 and current weight to 0.
4. Iterate through the sorted items and do the following:
   • Add item to knapsack if its weight is less than or equal to the residual capacity of the knapsack. Update current weight and total value accordingly.
   • If item cannot be added to the knapsack in full, add the fraction of it that fits in the knapsack. Also, update current weight and total value accordingly.
5. Repeat until the knapsack is fully loaded.

Example Code in Python:

class ItemValue:
    """Item Value DataClass"""
    def __init__(self, wt, val, ind):
        self.wt = wt
        self.val = val
        self.ind = ind
        self.cost = val / wt

    def __lt__(self, other):
        return self.cost < other.cost

def fractional_knapsack(capacity, weights, values):
    """Function to get maximum value."""
    item_value = []
    for i in range(len(weights)):
        item_value.append(ItemValue(weights[i], values[i], i))
    
    # Sort item_value by cost in descending order.
    item_value.sort(reverse=True)
    
    total_value = 0.0
    
    for i in item_value:
        current_wt = int(i.wt)
        current_val = int(i.val)
        
        if capacity - current_wt >= 0:
            capacity -= current_wt
            total_value += current_val
        else:
            fraction = capacity / current_wt
            total_value += current_val * fraction
            capacity = int(capacity - (current_wt * fraction))
            
        return total_value

weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50

max_value_in_knapsack = fractional_knapsack(capacity, weights, values)
print(f"Maximum total value in Knapsack = {max_value_in_knapsack}")

Input:

• weights: [10, 20, 30]
• values: [60, 100, 120]
• capacity: 50

Output:

• Maximum total value in Knapsack = 240.0

Example 3: Coin Change Problem (Greedy Approach)

Given an unlimited supply of coins of given denominations, find the minimum number of coins needed to make the change.

Steps:

1. Sort the coin denominations in descending order.
2. Start iterating from the largest denomination to the smallest, using as many coins of this denomination as possible without exceeding the amount.
3. Reduce the amount by the total worth of coins taken.
4. Repeat steps 2 and 3 until no amount is remaining.

Limitation of Greedy Approach:

The greedy approach does not guarantee an optimal solution in the general coin change problem (where any denominations are possible). However, it works optimally in standard coins with denominations like 1, 5, 10, and 25.

Example Code in Python:

def coin_change_greedy(denominations, amount):
    # Initialize result list
    result = []
    
    # Sort the denominations in descending order
    denominations = sorted(denominations, reverse=True)
    
    # Iterate over the denominations
    for coin in denominations:
        if amount == 0:
            break
        count = amount // coin
        amount -= count * coin
        for _ in range(count):
            result.append(coin)
    
    return result

# Standard U.S. coin denominations
denominations = [25, 10, 5, 1]
amount = 63

change = coin_change_greedy(denominations, amount)
print(f"The coins selected are: {change}")

Input:

• denominations: [25, 10, 5, 1]
• amount: 63

Output:

• The coins selected are: [25, 25, 10, 1, 1, 1]

This shows that for an amount of 63, using denominations 25, 10, 5, and 1, the greedy approach uses 6 coins.

Summary

Greedy algorithms are simple and efficient for certain optimization problems. They make optimal choices at each step to ensure the best global solution. Key characteristics include:

• Making the locally optimal choice.
• Solving subproblems individually to build a global solution.
• No backtracking needed – once a choice is made, it is final.

Examples where greedy algorithms are applicable include:

• Activity Selection Problem.
• Fractional KnapSack Problem.
• Coin Change Problem with specific denominations.