Greedy Introduction 🎯

Welcome to a fascinating journey into the world of Greedy Algorithms! This lesson is designed to help both beginners and intermediate learners understand and apply this powerful technique in their coding projects. 📝

What are Greedy Algorithms? 💡

Greedy algorithms are a type of problem-solving approach used in computer science to find an approximate solution to optimization problems. They work by making the locally optimal choice at each stage with the hope that this choice will lead to a global optimum.

Key Features 📝

Locally Optimal: At each step, make the choice that seems best without considering the impact of the choice on future steps.
Near-Optimal: Although not always guaranteed to produce the global optimum, greedy algorithms often find a near-optimal solution.
Efficient: Greedy algorithms are usually fast and can handle large data sets.

Real-World Examples 📝

Kruskal's Algorithm: For minimum spanning tree in a graph.
Huffman Coding: For data compression.
Dijkstra's Algorithm: For finding shortest paths in a graph.

Greedy Algorithm Steps 📝

Initiate: Start with an empty solution or an initial, feasible solution.
Choose: At each step, choose the local best option that appears most promising for the global optimum.
Verify: Once the solution is complete, verify if the chosen local optimal solution is indeed the global optimal solution.

Greedy Algorithms in Practice 💡

Let's dive into two examples to better understand the concept.

Example 1: Activity Selection Problem 📝

Given a list of activities with their start and end times, choose the maximum number of activities that don't overlap.

python

activities = [(1, 4), (2, 3), (0, 1), (2, 5), (3, 4), (0, 2), (6, 8)]

activities.sort(key=lambda x: x[1])  # Sort by end time
selected_activities = []
current_end = -1

for activity in activities:
    start, end = activity
    if start >= current_end:
        selected_activities.append(activity)
        current_end = end

print(len(selected_activities))  # Output: 4

In this example, we first sort the activities by their end times. At each step, we consider the next activity and check if its start time is greater than or equal to the current end time of the previously selected activity. If so, we add the new activity to our selection and update the current end time.

Example 2: Knapsack Problem 💡

Given a set of items with weights and values, find the items to include in a knapsack of limited capacity to maximize total value.

python

items = [(3, 4), (1, 2), (6, 5), (5, 6)]
capacity = 9

items.sort(key=lambda x: x[1]/x[0], reverse=True)  # Sort by value/weight ratio
knapsack = []
current_weight = 0

for item in items:
    weight, value = item
    if current_weight + weight <= capacity:
        knapsack.append(item)
        current_weight += weight

print(sum([item[1] for item in knapsack]))  # Output: 13

In this example, we first sort the items by their value-to-weight ratio. At each step, we consider the next item and check if adding it won't exceed the current knapsack capacity. If not, we add the item to our selection and update the current weight.

Quiz 💡

With these examples, we hope you now have a better understanding of what greedy algorithms are and how they can be used in practice. Happy coding! 💡🎯