Day 40: Introduction to Greedy Algorithms#

Welcome to Day 40 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Greedy Algorithms, a powerful problem-solving approach used in optimization problems.

What are Greedy Algorithms?#

Greedy algorithms are a simple, intuitive class of algorithms that make the locally optimal choice at each step with the hope of finding a global optimum. In other words, a greedy algorithm never reconsiders its choices - it simply makes the best choice it can at each step.

Key Characteristics of Greedy Algorithms#

1. Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.
2. Optimal Substructure: An optimal solution to the problem contains optimal solutions to subproblems.

When to Use Greedy Algorithms#

Greedy algorithms are ideal for optimization problems. They are especially useful when the problem has the following properties:

1. Greedy choice property
2. Optimal substructure
3. Safe move (the move does not prevent the algorithm from finding the optimal solution)

Example: Coin Change Problem (Greedy Approach)#

Let’s solve the coin change problem using a greedy approach:

 1def coin_change_greedy(coins, amount):
 2    coins.sort(reverse=True)  # Sort coins in descending order
 3    coin_count = 0
 4    coin_used = []
 5    
 6    for coin in coins:
 7        while amount >= coin:
 8            amount -= coin
 9            coin_count += 1
10            coin_used.append(coin)
11    
12    if amount == 0:
13        return coin_count, coin_used
14    else:
15        return -1, []  # Cannot make exact change
16
17# Example usage
18coins = [25, 10, 5, 1]  # Coin denominations
19amount = 63
20count, used = coin_change_greedy(coins, amount)
21if count != -1:
22    print(f"Minimum coins needed: {count}")
23    print(f"Coins used: {used}")
24else:
25    print("Cannot make exact change")

Note: This greedy approach works for the US coin system but may not work for all coin systems.

Advantages of Greedy Algorithms#

1. Simple and easy to implement
2. Often very efficient in terms of time complexity
3. Can provide good approximations to NP-complete problems

Disadvantages of Greedy Algorithms#

1. May not always find the globally optimal solution
2. Difficult to prove correctness for some problems

Common Greedy Algorithms#

1. Kruskal’s Algorithm for Minimum Spanning Tree
2. Dijkstra’s Algorithm for Shortest Path
3. Huffman Coding for Data Compression
4. Activity Selection Problem

Example: Activity Selection Problem#

Let’s implement the Activity Selection Problem using a greedy approach:

 1def activity_selection(start, finish):
 2    n = len(start)
 3    
 4    # Sort activities by finish time
 5    activities = sorted(zip(start, finish), key=lambda x: x[1])
 6    
 7    selected = [0]  # First activity is always selected
 8    last_finish = activities[0][1]
 9    
10    for i in range(1, n):
11        if activities[i][0] >= last_finish:
12            selected.append(i)
13            last_finish = activities[i][1]
14    
15    return selected
16
17# Example usage
18start = [1, 3, 0, 5, 8, 5]
19finish = [2, 4, 6, 7, 9, 9]
20selected = activity_selection(start, finish)
21print("Selected activities:", selected)

Exercise#

1. Implement the Fractional Knapsack Problem using a greedy approach.

2. Solve the Job Sequencing Problem with deadlines using a greedy algorithm.

3. Implement Huffman Coding for data compression.

Summary#

Today, we introduced Greedy Algorithms, a powerful problem-solving technique for optimization problems. We discussed their characteristics, advantages, and limitations. We also implemented solutions for the Coin Change Problem and the Activity Selection Problem using greedy approaches.

Understanding when and how to apply greedy algorithms is crucial for solving a wide range of optimization problems efficiently. However, it’s important to remember that greedy algorithms don’t always guarantee the optimal solution for every problem.

Tomorrow, we’ll dive into more complex greedy algorithms and their applications. Stay tuned!

Solution#

 1def fractional_knapsack(W, wt, val):
 2    # Sort items by value-to-weight ratio, highest first
 3    items = sorted(zip(val, wt), key=lambda x: x[0] / x[1], reverse=True)
 4    total_value = 0.0
 5    remaining = W
 6    for value, weight in items:
 7        if remaining <= 0:
 8            break
 9        if weight <= remaining:
10            total_value += value          # take the whole item
11            remaining -= weight
12        else:
13            total_value += value * (remaining / weight)  # take a fraction
14            remaining = 0
15    return total_value
16
17# Example usage
18val = [60, 100, 120]
19wt = [10, 20, 30]
20W = 50
21print(f"Maximum value: {fractional_knapsack(W, wt, val)}")  # 240.0