Greedy Method: General Explanation and Example
1. Introduction to the Greedy Method
The Greedy Method is an algorithmic paradigm used to solve optimization problems. It builds up a
solution piece by piece, always choosing the next piece that offers the most immediate benefit. This
approach does not always yield the optimal solution for all problems, but it works well for many, especially
those that have the "greedy-choice property" and "optimal substructure."
Greedy-Choice Property: A global optimal solution can be arrived at by selecting a local optimal choice.
Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.
2. General Steps of the Greedy Method
Define the Problem: Clearly understand the problem and what needs to be optimized.
Choose the Greedy Strategy: Determine the criteria for making the greedy choice (e.g., selecting the
largest, smallest, earliest, etc.).
Prove the Greedy Choice is Safe: Show that making a local optimal choice does not preclude the
possibility of finding the global optimum.
Construct a Solution: Build the solution iteratively by making a series of greedy choices.
Analyze: Evaluate the efficiency of the algorithm, usually in terms of time and space complexity.
3. Example: Coin Change Problem
Problem Statement: Given a set of coin denominations and an amount of money, determine the minimum
number of coins required to make up that amount.
Denominations Available: 1, 5, 10, 25 (U.S. coin denominations)
Amount to Change: 63 cents
Step-by-Step Solution:
Greedy Strategy: Always pick the largest denomination that does not exceed the remaining amount.
Procedure:
Start with 63 cents.
Choose the largest coin ≤ 63, which is 25. Subtract 25 from 63, leaving 38.
Choose the largest coin ≤ 38, which is 25. Subtract 25 from 38, leaving 13.
Choose the largest coin ≤ 13, which is 10. Subtract 10 from 13, leaving 3.
Choose the largest coin ≤ 3, which is 1. Subtract 1 from 3, leaving 2.
Repeat until the remaining amount is 0.
Solution:
Number of coins used: 3 (25 + 25 + 10 + 1 + 1 + 1)
Output: Minimum number of coins required is 6.
Algorithm:
function minCoins(coins, n, amount):
sort(coins in descending order)
count = 0
for i = 0 to n-1:
while amount >= coins[i]:
amount = amount - coins[i]
count = count + 1
return count
Explanation:
Step 1: Sort the coins in descending order.
Step 2: Start from the largest coin and keep subtracting it from the amount until the amount becomes
smaller than the coin value.
, Step 3: Move to the next largest coin and repeat until the amount is zero.
4. Limitations
The Greedy Method may not always give the optimal solution for every problem. For instance, if the coin
denominations were 1, 3, and 4, and the amount was 6, a greedy approach would pick coins (4, 1, 1),
which totals 3 coins. However, the optimal solution is (3, 3), which totals 2 coins.
5. Applications of the Greedy Method
Activity Selection Problem: Selecting the maximum number of activities that don't overlap.
Huffman Coding: Creating an optimal prefix code.
Kruskal’s and Prim’s Algorithms: Finding a minimum spanning tree in a graph.
Dijkstra’s Algorithm: Finding the shortest path in a graph.
--------------------------------------------------------------------------------------------------------------------------------------------
----------
Job Sequencing with Deadlines Using the Greedy Method
1. Introduction to Job Sequencing with Deadlines
Job sequencing with deadlines is a classic optimization problem where the objective is to maximize the
total profit earned by performing a set of jobs, each with a specific deadline and profit. The jobs need to
be completed within their deadlines, and each job takes exactly one unit of time. The goal is to find the
optimal sequence of jobs that maximizes the total profit.
2. Problem Statement
Input: A set of jobs, each with a deadline and a profit.
Output: A sequence of jobs that maximizes the total profit while ensuring that each job is completed within
its deadline.
3. Assumptions
Each job takes exactly one unit of time.
A job can only be completed if it is started before its deadline.
Only one job can be processed at a time.
4. Greedy Approach
The greedy strategy to solve the job sequencing problem involves the following steps:
Sort the Jobs: Arrange the jobs in decreasing order of profit.
Select Jobs: Iterate over the sorted jobs and schedule each job at the latest available slot before its
deadline. If no such slot is available, skip the job.
5. Example
Consider the following set of jobs:
Job Deadline Profit
J1 4 100
J2 1 19
J3 2 27
J4 1 25
J5 3 15
Step-by-Step Solution:
Sort Jobs by Profit:
Sorted Jobs: J1, J3, J4, J5, J2
Schedule Jobs:
Schedule J1 at slot 4 (its deadline).
Schedule J3 at slot 2 (its deadline).
1. Introduction to the Greedy Method
The Greedy Method is an algorithmic paradigm used to solve optimization problems. It builds up a
solution piece by piece, always choosing the next piece that offers the most immediate benefit. This
approach does not always yield the optimal solution for all problems, but it works well for many, especially
those that have the "greedy-choice property" and "optimal substructure."
Greedy-Choice Property: A global optimal solution can be arrived at by selecting a local optimal choice.
Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.
2. General Steps of the Greedy Method
Define the Problem: Clearly understand the problem and what needs to be optimized.
Choose the Greedy Strategy: Determine the criteria for making the greedy choice (e.g., selecting the
largest, smallest, earliest, etc.).
Prove the Greedy Choice is Safe: Show that making a local optimal choice does not preclude the
possibility of finding the global optimum.
Construct a Solution: Build the solution iteratively by making a series of greedy choices.
Analyze: Evaluate the efficiency of the algorithm, usually in terms of time and space complexity.
3. Example: Coin Change Problem
Problem Statement: Given a set of coin denominations and an amount of money, determine the minimum
number of coins required to make up that amount.
Denominations Available: 1, 5, 10, 25 (U.S. coin denominations)
Amount to Change: 63 cents
Step-by-Step Solution:
Greedy Strategy: Always pick the largest denomination that does not exceed the remaining amount.
Procedure:
Start with 63 cents.
Choose the largest coin ≤ 63, which is 25. Subtract 25 from 63, leaving 38.
Choose the largest coin ≤ 38, which is 25. Subtract 25 from 38, leaving 13.
Choose the largest coin ≤ 13, which is 10. Subtract 10 from 13, leaving 3.
Choose the largest coin ≤ 3, which is 1. Subtract 1 from 3, leaving 2.
Repeat until the remaining amount is 0.
Solution:
Number of coins used: 3 (25 + 25 + 10 + 1 + 1 + 1)
Output: Minimum number of coins required is 6.
Algorithm:
function minCoins(coins, n, amount):
sort(coins in descending order)
count = 0
for i = 0 to n-1:
while amount >= coins[i]:
amount = amount - coins[i]
count = count + 1
return count
Explanation:
Step 1: Sort the coins in descending order.
Step 2: Start from the largest coin and keep subtracting it from the amount until the amount becomes
smaller than the coin value.
, Step 3: Move to the next largest coin and repeat until the amount is zero.
4. Limitations
The Greedy Method may not always give the optimal solution for every problem. For instance, if the coin
denominations were 1, 3, and 4, and the amount was 6, a greedy approach would pick coins (4, 1, 1),
which totals 3 coins. However, the optimal solution is (3, 3), which totals 2 coins.
5. Applications of the Greedy Method
Activity Selection Problem: Selecting the maximum number of activities that don't overlap.
Huffman Coding: Creating an optimal prefix code.
Kruskal’s and Prim’s Algorithms: Finding a minimum spanning tree in a graph.
Dijkstra’s Algorithm: Finding the shortest path in a graph.
--------------------------------------------------------------------------------------------------------------------------------------------
----------
Job Sequencing with Deadlines Using the Greedy Method
1. Introduction to Job Sequencing with Deadlines
Job sequencing with deadlines is a classic optimization problem where the objective is to maximize the
total profit earned by performing a set of jobs, each with a specific deadline and profit. The jobs need to
be completed within their deadlines, and each job takes exactly one unit of time. The goal is to find the
optimal sequence of jobs that maximizes the total profit.
2. Problem Statement
Input: A set of jobs, each with a deadline and a profit.
Output: A sequence of jobs that maximizes the total profit while ensuring that each job is completed within
its deadline.
3. Assumptions
Each job takes exactly one unit of time.
A job can only be completed if it is started before its deadline.
Only one job can be processed at a time.
4. Greedy Approach
The greedy strategy to solve the job sequencing problem involves the following steps:
Sort the Jobs: Arrange the jobs in decreasing order of profit.
Select Jobs: Iterate over the sorted jobs and schedule each job at the latest available slot before its
deadline. If no such slot is available, skip the job.
5. Example
Consider the following set of jobs:
Job Deadline Profit
J1 4 100
J2 1 19
J3 2 27
J4 1 25
J5 3 15
Step-by-Step Solution:
Sort Jobs by Profit:
Sorted Jobs: J1, J3, J4, J5, J2
Schedule Jobs:
Schedule J1 at slot 4 (its deadline).
Schedule J3 at slot 2 (its deadline).
