Greedy Problems Master List 🎯

Welcome to the Greedy Problems Master List! In this comprehensive guide, we'll delve into the world of Greedy Algorithms, a powerful and efficient approach to solving optimization problems. By the end of this lesson, you'll have a solid understanding of the concept and be able to apply it to various real-world scenarios. 📝

What are Greedy Algorithms? 💡

Greedy algorithms make the locally optimal choice at each stage with the hope of finding a global optimum. They are simple, easy to implement, and often very efficient. Let's break it down:

Locally Optimal: At each step, we choose the best solution available at that moment.
Global Optimum: The goal is to reach a global optimum (the best overall solution) by making the best local choices.

Why use Greedy Algorithms? 📝

Greedy algorithms are useful when:

The problem can be broken down into smaller, independent decisions.
The locally optimal solution is also the global optimal solution.
The problem can be solved quickly by making a sequence of good decisions.

Greedy Algorithms Types 💡

There are two types of Greedy Algorithms:

Non-Adaptive Greedy Algorithms: These algorithms make their decisions without considering any future decisions.
Adaptive Greedy Algorithms: These algorithms make their decisions considering some future decisions.

Greedy Algorithms Examples 💡

Let's dive into two practical examples to illustrate how Greedy Algorithms work:

Example 1: Activity Selection Problem 🎯

Given a set of activities, each with a start and end time, we want to select the maximum number of non-overlapping activities.

python

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

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

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

    return selected_activities

print(greedy_activity_selection(activities))

Example 2: Knapsack Problem 🎯

Given a set of items with weights and values, we want to select items that maximize the total value without exceeding a given weight limit.

python

items = [(60, 30), (100, 60), (120, 70), (160, 80), (180, 120)]
capacity = 300

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

    for weight, value in items:
        if weight + sum(item[0] for item in selected_items) <= capacity:
            selected_items.append((weight, value))

    return sum(item[1] for item in selected_items)

print(greedy_knapsack(items, capacity))

Happy coding, and remember: patience, practice, and perseverance are the keys to mastering Greedy Algorithms! 🚀