YouTip

Greedy Algorithm

Greedy algorithm (English: greedy algorithm), also known as the greedy algorithm, is an algorithmic strategy that, at each step, selects the best or optimal (i.e., most advantageous) choice under the current state, hoping to lead to a globally optimal result.

Greedy algorithm is like what we often say: focusing only on immediate benefits, without considering overall optimality; the choices made are merely locally optimal solutions in some sense.

\n

Imagine you have a pile of coins with different denominations (e.g., ¥1, ¥0.5, ¥0.1), and you need to make exactly ¥1.8 using the minimum number of coins.

\n \n

A natural idea is: always take the coin with the largest denomination first.

\n \n

First take ¥1, leaving ¥0.8; then take ¥0.5, leaving ¥0.3; finally take three ¥0.1 coins.

\n \n

Throughout this process, at every step we made the best choice available at that moment—this is the core idea of the greedy algorithm.\n

\n

Greedy algorithm is like a short-sighted but decisive person:

\n
• Each step selection: Make the seemingly optimal choice under the current state
\n
• No global consideration: Do not consider how this choice affects future steps
\n
• Expected outcome: Hope that local optimal choices will lead to a globally optimal solution
\n

Real-world examples:

\n
• Change-making: Always use the largest denomination coin first
\n
• Hill climbing: Always move in the steepest direction
\n
• Shopping: Always buy the currently most discounted item
\n
• Route selection: Always choose the currently shortest path
\n

Characteristics of Greedy Algorithms

\n
• Greedy Choice Property: The optimal solution at each step can be derived from the previous locally optimal solutions. Later choices do not affect earlier ones.
\n
• Optimal Substructure: The optimal solution to a problem contains optimal solutions to its subproblems. This property is also shared by dynamic programming, but greedy algorithms "greedily" select the optimal solution for each subproblem at every step.
\n

Difference from Dynamic Programming

This is a common point of confusion for beginners. Let’s compare them using a table:

In simple terms, dynamic programming is “plan thoroughly before acting”, sacrificing immediate gains for long-term benefit; whereas greedy algorithm is “enjoy the present moment”, pursuing only immediate benefits.

Basic Framework of Greedy Algorithm

The greedy algorithm does not have a fixed code template, but its idea can be summarized into the following steps:

\n
1. Establish a mathematical model: Abstract the real-world problem into a mathematical one.
\n
2. Define the greedy strategy: Determine the criterion for selecting the “optimal solution” at each step. This is the core and difficulty of the algorithm.
\n
3. Prove the greedy strategy: Prove that the defined greedy strategy leads to a globally optimal solution (optional but important; for algorithm problems, understanding correctness is usually required).
\n
4. Iterative solution: Starting from the initial state, make greedy choices step by step according to the strategy until the problem is solved.
\n

A general pseudocode framework is as follows:

Example

def greedy_algorithm(problem):\n\n# 1. Initialization: may include sorting, creating result containers, etc.\n\n solution =[]\n\n# 2. Iterate through all options, usually requiring sorting by a certain rule first\n\nfor item in sorted(problem.items, key=Greedy Strategy Rules):\n\n# 3. Greedy selection: if the current choice satisfies the condition, adopt it\n\nif is_feasible(solution, item):\n\n solution.append(item)\n\n# 4. Return the final constructed solution\n\nreturn solution\n

Classic Problems and Code Examples

Let’s experience the application of greedy algorithms through several classic problems. For each problem, we will: 1) analyze the problem and greedy strategy; 2) provide complete code; 3) explain line by line.

Example 1: Coin Change Problem

Problem Description: Assume the coin system is [100, 50, 20, 10, 5, 1] (unit: cents), and you need to make change for amount cents. Find the minimum number of coins required.

Greedy Strategy: At each step, select the largest coin whose denomination does not exceed the remaining amount. For the Chinese RMB system, this strategy is effective.

Code Implementation:

Example

def coin_change_greedy(coins, amount):\n\n"""\n\n Use greedy algorithm to solve the coin change problem (for specific coin systems)\n\n :param coins: list, list of coin denominations, should be sorted in descending order\n\n :param amount: int, total amount to make change for\n\n :return: list, list of coin denominations used\n\n """\n\n coins.sort(reverse=True)# Ensure coins are sorted from largest to smallest denomination\n\n result =[]# Container for coins used in change\n\n remaining = amount # Remaining amount to make change for\n\nfor coin in coins:\n\n# When the current coin denomination is less than or equal to the remaining amount, use it as much as possible\n\nwhile remaining >= coin:\n\n result.append(coin)\n\n remaining -= coin # Subtract the current coin denomination from remaining amount\n\n# Check if exact change is made\n\nif remaining ==0:\n\nreturn result\n\nelse:\n\n# For cases where exact change cannot be made (though won’t happen in this coin system)\n\nreturn None\n\n# Test data\n\n test_coins =[100,50,20,10,5,1]\n\n test_amount =186# ¥1.86\n\nchange = coin_change_greedy(test_coins, test_amount)\n\nprint(f"Making change for {test_amount} cents requires coins: {change}")\n\nprint(f"Number of coins: {len(change)}")\n\n# Output: Making change for 186 cents requires coins: [100, 50, 20, 10, 5, 1]\n\n# Number of coins: 6\n

Code Explanation:

\n
• Line 8: coins.sort(reverse=True) is the key preparation for the greedy strategy, ensuring we always consider larger denomination coins first.
\n
• Lines 12–15: The while loop ensures that as long as the current denomination can still be used, we keep using it—implementing the “use as many as possible” greedy choice.
\n
• Lines 18–22: Check the final result to ensure the amount matches exactly.
\n

Important Note: The greedy algorithm for the coin change problem does not always yield the optimal solution**! For example, if the coin system is [25, 20, 10, 5, 1] and you need to make 40 cents, the greedy method chooses 25+10+5 (three coins), but the optimal solution is 20+20 (two coins). Only for specific currency systems (like RMB) is the greedy strategy valid.

def interval_scheduling(intervals):\n\n"""\n\n Solve the maximum non-overlapping intervals problem (interval scheduling)\n\n :param intervals: list of [start, end], list of intervals\n\n :return: list of [start, end], list of selected intervals\n\n """\n\n# 1. Sort by end time in ascending order\n\n intervals_sorted =sorted(intervals, key=lambda x: x)\n\nselected =[]# Store selected intervals\n\n last_end_time = -float('inf')# Initialize the end time of the last selected interval\n\nfor interval in intervals_sorted:\n\n start, end = interval\n\n# 2. Greedy selection: if the current interval's start time is not earlier than the last selected interval's end time, select it\n\nif start >= last_end_time:\n\n selected.append(interval)\n\n last_end_time = end # Update the latest end time\n\nreturn selected\n\n# Test data: each sublist represents a meeting [start time, end time]\n\n test_intervals =[\n\n[1,3],[2,4],[3,5],[4,6],[5,7],\n\n[1,2],[2,3],[1,4]\n\n]\n\nresult = interval_scheduling(test_intervals)\n\nprint("Maximum number of meetings that can be scheduled (after sorting by end time):")\n\nfor meeting in result:\n\nprint(f"  Meeting [{meeting}, {meeting}]")\n\nprint(f"Total: {len(result)} meetings")\n\n# One possible output (order may vary after sorting, but count is optimal):\n\n# Meeting [1, 2]\n\n# Meeting [2, 3]\n\n# Meeting [3, 5] or [4, 6], etc.\n\n# Total: 4 meetings\n

import heapq\n\nclass Node:\n\n"""Node class for Huffman tree"""\n\ndef __init__ (self, char, freq):\n\nself.char= char # Character (only leaf nodes have this)\n\nself.freq= freq # Frequency\n\nself.left=None\n\nself.right=None\n\n# Define comparison method to allow comparison in heap\n\ndef __lt__ (self, other):\n\nreturn self.freq< other.freq\n\ndef build_huffman_tree(char_freq):\n\n"""\n\n Build Huffman tree\n\n :param char_freq: dict, characters and their frequencies, e.g., {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}\n\n :return: Node, root node of the Huffman tree\n\n """\n\n# 1. Initialization: create a leaf node for each character and put them into a min-heap (priority queue)\n\n heap =[Node(char, freq)for char, freq in char_freq.items()]\n\nheapq.heapify(heap)# Convert list into a min-heap\n\n# 2. Greedy merging: while more than one node remains in the heap\n\nwhile len(heap)>1:\n\n# Pop two nodes with smallest frequencies\n\n left =heapq.heappop(heap)\n\n right =heapq.heappop(heap)\n\n# Create a new internal node whose frequency is the sum of its children's frequencies\n\n merged = Node(None, left.freq + right.freq)\n\n merged.left= left\n\n merged.right= right\n\n# Push the new node back into the heap\n\nheapq.heappush(heap, merged)\n\n# The last remaining node in the heap is the root of the Huffman tree\n\nreturn heapif heap else None\n\n# Test data\n\n test_freq ={'a': 5,'b': 9,'c': 12,'d': 13,'e': 16,'f': 45}\n\n root = build_huffman_tree(test_freq)\n\nprint("Huffman tree built successfully! Root node frequency =", root.freq if root else 0)\n\n# Output: Huffman tree built successfully! Root node frequency = 100\n