Greedy Algorithms

What You’ll Learn 📚

• Understanding the core concept of greedy algorithms
• Key terminology and definitions
• Simple to complex examples with explanations
• Common questions and answers
• Troubleshooting tips for common issues

Introduction to Greedy Algorithms

Greedy algorithms are a class of algorithms that make the locally optimal choice at each stage with the hope of finding a global optimum. They are called ‘greedy’ because they make the best choice at each step without considering the bigger picture. This approach can be incredibly efficient and is often used in optimization problems.

Think of a greedy algorithm like a person picking the largest fruit from a tree without considering the overall weight of the basket. 🍎

Key Terminology

• Greedy Choice Property: The choice that looks the best at the moment.
• Optimal Substructure: A problem has an optimal substructure if an optimal solution to the problem contains optimal solutions to the subproblems.
• Local Optimum: The best solution in a small, localized area.
• Global Optimum: The best solution overall.

Simple Example: Coin Change Problem

def min_coins(coins, amount):
    coins.sort(reverse=True)  # Sort coins in descending order
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count

coins = [1, 5, 10]
amount = 18
print(min_coins(coins, amount))  # Output: 4

Progressively Complex Examples

Example 1: Activity Selection Problem

Given a set of activities with start and end times, select the maximum number of activities that don’t overlap.

JavaScript Example

function activitySelection(activities) {
    activities.sort((a, b) => a.end - b.end);
    let count = 0;
    let lastEnd = 0;
    for (let activity of activities) {
        if (activity.start >= lastEnd) {
            count++;
            lastEnd = activity.end;
        }
    }
    return count;
}

const activities = [
    { start: 1, end: 3 },
    { start: 2, end: 4 },
    { start: 3, end: 5 },
    { start: 0, end: 6 },
    { start: 5, end: 7 },
    { start: 8, end: 9 }
];
console.log(activitySelection(activities));  // Output: 4

Example 2: Fractional Knapsack Problem

Given weights and values of items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Python Example

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight

    def value_per_weight(self):
        return self.value / self.weight

items = [Item(60, 10), Item(100, 20), Item(120, 30)]
capacity = 50

items.sort(key=lambda x: x.value_per_weight(), reverse=True)

total_value = 0
for item in items:
    if capacity - item.weight >= 0:
        capacity -= item.weight
        total_value += item.value
    else:
        total_value += item.value_per_weight() * capacity
        break

print(total_value)  # Output: 240.0