Greedy Method in Algorithm Design

What is the Greedy Method?

The greedy method is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit or looks best at the moment. It does not look back or reconsider choices once made.

Properties of Greedy Algorithms

Example 1: Fractional Knapsack Problem

This problem allows taking fractions of items to maximize total value in a knapsack with limited capacity.

def fractional_knapsack(values, weights, capacity):
    index = list(range(len(values)))
    ratio = [v / w for v, w in zip(values, weights)]
    index.sort(key=lambda i: ratio[i], reverse=True)

    max_value = 0
    for i in index:
        if weights[i] <= capacity:
            capacity -= weights[i]
            max_value += values[i]
        else:
            fraction = capacity / weights[i]
            max_value += values[i] * fraction
            break
    return max_value

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print("Max value in Knapsack =", fractional_knapsack(values, weights, capacity))  # Output: 240.0

Example 2: Dijkstra’s Shortest Path Algorithm

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph by greedily choosing the next closest node.

import heapq

def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    while queue:
        curr_distance, curr_node = heapq.heappop(queue)
        if curr_distance > distances[curr_node]:
            continue
        for neighbor, weight in graph[curr_node].items():
            distance = curr_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

graph = {
    'A': {'B': 10, 'C': 5},
    'B': {'C': 2, 'D': 1},
    'C': {'B': 3, 'D': 9, 'E': 2},
    'D': {'E': 4},
    'E': {'D': 6, 'A': 7}
}

print(dijkstra(graph, 'A'))

When to Use Greedy Algorithms?

Advantages and Disadvantages