In the context of algorithms and problem-solving, Greedy is a heuristic approach where a decision is made at each step to select the locally optimal choice in the hope of finding a globally optimal solution. The greedy algorithm makes the best possible choice at each step without considering the overall consequences or looking ahead to the future steps.
The Greedy strategy is widely used in various optimization problems where the goal is to find the best possible solution from a set of choices. While it may not always guarantee an optimal solution for every problem, it often provides reasonably good solutions and has the advantage of being simple and easy to implement.
Greedy algorithms work well when the problem exhibits the “greedy choice property,” which means that making a locally optimal choice at each step leads to a globally optimal solution. However, it’s essential to be cautious while applying the Greedy approach as some problems might require more sophisticated techniques like dynamic programming or backtracking to find the optimal solution.
Keep in mind that while Greedy algorithms can be simple and effective, they may not always yield the optimal solution for every problem. It’s essential to understand the problem’s characteristics and the properties of the Greedy approach to decide whether it is suitable for a specific problem or not.
Let’s solve some classic problems using Greedy strategy.
A classic example of the Greedy algorithm is the “Coin Change” problem. Given a set of coin denominations and a target amount, the goal is to find the minimum number of coins needed to make up that amount.
def coin_change(coins, amount):
# sort the coins in descending order
coins.sort(reverse=True)
# initialize i to point to the first coin
i = 0
# initialize ans to store the chosen coins
ans = []
# while amount is positive
while amount > 0:
# if current coin is smaller than or equal to amount
if coins[i] <= amount:
# append it to ans and subtract it from amount
ans.append(coins[i])
amount -= coins[i]
# otherwise, increment i to point to next coin
else:
i += 1
# return ans as the list of chosen coins
return ans
# examples
coins = [1, 5, 10, 25]
target_amount = 37
print(coin_change(coins, target_amount)) # [25, 10, 1, 1]
coins = [1, 2, 5, 10, 20, 50]
target_amount = 93
print(coin_change(coins, target_amount)) # [50, 20, 20, 2, 1]In this example, the Greedy algorithm starts by using the largest denominations first, as it often provides the optimal solution. The algorithm repeatedly subtracts the largest denomination from the target amount until it cannot do so anymore. The result is the minimum number of coins needed to make up the target amount.
However, this algorithm does not always produce the optimal solution, as it may miss some combinations of smaller coins that require fewer coins in total. For example, if the amount is 12 and the coins are [2, 3, 6, 7], the greedy algorithm will choose [7, 3, 2] which requires three coins, while the optimal solution is [6, 6] which requires only two coins.
Another classic example of a greedy problem is the “Activity Selection” problem, which is a scheduling problem.
Problem statement: Given a list of activities, each having a start time and end time, select the maximum number of non-overlapping activities that can be performed by a single person. The person can only work on one activity at a time, and you want to maximize the number of activities performed.
Greedy approach: To solve this problem using the greedy approach, we can sort the activities based on their finish times and then iteratively select the activities with the earliest finish times that do not overlap with the previously selected activities.
def activity_selection(activities):
if not activities:
return []
# sort activities based on finish times
activities.sort(key=lambda x: x[1])
# initialize the selected activities with the first one
selected_activities = [activities[0]]
for activity in activities[1:]:
start_time, end_time = activity
prev_activity = selected_activities[-1]
prev_end_time = prev_activity[1]
if start_time >= prev_end_time:
selected_activities.append(activity)
return selected_activities
# examples
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
selected_activities = activity_selection(activities)
print(selected_activities) # [(1, 4), (5, 7), (8, 11), (12, 16)]In this example, the Greedy algorithm selects activities based on their finish times. It starts by sorting the activities in ascending order of finish times. The algorithm then iterates through the sorted activities and adds an activity to the selected list if its start time is after or equal to the end time of the previously selected activity.
The Greedy approach ensures that we always select the activity with the earliest finish time that is compatible with the previously selected activities. By doing so, we maximize the number of non-overlapping activities that can be performed by a single person.
Another classic example of a greedy problem is the “Fractional Knapsack” problem. It is a variation of the traditional Knapsack problem, where you have a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. The goal is to maximize the total value of the items that can be put into the knapsack without exceeding its weight capacity.
In the Fractional Knapsack problem, you can take fractional parts of an item if you cannot take the whole item. This means that you can take a fraction of an item’s weight to maximize the total value.
Greedy approach: To solve this problem using the greedy approach, you can sort the items based on their value-to-weight ratios in descending order. Then, you iteratively select items with the highest value-to-weight ratio until the knapsack is full.
def fractional_knapsack(items, capacity):
# sort items based on value-to-weight ratio in descending order
items.sort(key=lambda x: x[1] / x[0], reverse=True)
total_value = 0
knapsack = []
for weight, value in items:
if capacity == 0:
break
elif capacity >= weight:
knapsack.append((weight, value))
total_value += value
capacity -= weight
else:
fraction = capacity / weight
knapsack.append((capacity, value * fraction))
total_value += value * fraction
capacity = 0
return total_value, knapsack
# examples
items = [(10, 60), (20, 100), (30, 120)]
knapsack_capacity = 50
max_value, selected_items = fractional_knapsack(items, knapsack_capacity)
print("Max Total Value:", max_value)
print("Selected Items:", selected_items)In this example, the Greedy algorithm selects items with the highest value-to-weight ratio first, as they contribute the most value relative to their weight. The algorithm iterates through the sorted items and adds items to the knapsack until it reaches the knapsack’s weight capacity.
The Greedy approach ensures that we maximize the total value of the items in the knapsack, even if we can take fractional parts of an item. Note that the Fractional Knapsack problem can be solved optimally using a Greedy approach, unlike the traditional Knapsack problem, where dynamic programming is required for an optimal solution.