DSA — Greedy Algorithms

What is a Greedy Algorithm?

Makes the locally optimal choice at each stage, hoping to find a global optimum.

Activity Selection Problem

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])
    selected = [activities[0]]
    
    for i in range(1, len(activities)):
        if activities[i][0] >= selected[-1][1]:
            selected.append(activities[i])
    
    return selected

Coin Change (Greedy)

def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count

Fractional Knapsack

def fractional_knapsack(weights, values, capacity):
    items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
    total = 0
    
    for value, weight in items:
        if capacity >= weight:
            total += value
            capacity -= weight
        else:
            total += value * (capacity / weight)
            break
    
    return total

When Greedy Works

Problem	Greedy Optimal?
Activity Selection	Yes
Fractional Knapsack	Yes
0/1 Knapsack	No
Huffman Coding	Yes

Mini Practice

1. Solve activity selection
2. Implement fractional knapsack
3. Create Huffman coding
4. Compare with dynamic programming

Up Next

Continue with Backtracking — exploring all possibilities.