Greedy Algorithm for Problem Solving

A Greedy Algorithm is a problem-solving approach that builds up a solution piece

by piece, always choosing the option that looks best at every step. It focuses on
making a sequence of locally optimal choices, with the hope that these decisions
will lead to a globally optimal solution.

Example: Traveling from Thiruvananthapuram to Ernakulam Using the

Greedy Approach

Let’s consider the task of traveling from Thiruvananthapuram to Ernakulam with multiple
available modes of transport: bike, car, bus, train, airplane, or even walking. The goal is to
select the mode of transport based on a set of constraints or objectives:

1. Minimizing Travel Time

2. Minimizing Cost
3. Satisfying Practical Constraints

Step 1: Apply the Greedy Approach

At each step, the greedy algorithm makes the locally optimal choice by filtering options
based on the immediate constraint.

Stage 1: Minimize Travel Time

To reach the destination quickly, we first prioritize speed.

 Available Options:
o Bike: 6 hours
o Car: 4.5 hours
o Bus: 5 hours
o Train: 3.5 hours
o Airplane: 1 hour
o Walking: 40 hours

Greedy Decision:
Select modes that satisfy the time constraint of reaching as quickly as possible. The airplane
(1 hour) is the fastest, followed by the train (3.5 hours).

Filter Outcome:
Airplane, Train.
Stage 2: Minimize Cost (Economical Constraint)

Among the remaining options, we now focus on minimizing cost.

 Cost of Airplane: ₹3,500

 Cost of Train: ₹500

Greedy Decision:
Select the train as it is cheaper and satisfies the economical constraint.

Filter Outcome:
Train.

Stage 3: Practical Constraints

Lastly, consider practical constraints like availability of tickets, comfort, or personal

preferences. If the train has tickets available and meets other needs, it will be chosen.

Final Decision

The algorithm selects the train as the final mode of transport based on:

1. Minimizing time (after filtering slower options).

2. Minimizing cost.
3. Satisfying practical constraints.

Greedy Approach Explanation

 Locally Optimal Choices: At each step, the algorithm optimizes for the immediate
constraint (time, cost, practicality) without revisiting earlier decisions.
 Global Solution: The sequence of locally optimal decisions leads to an efficient and
practical final solution.

Example: Coin Changing Problem

The Coin Changing Problem aims to find the minimum number of coins required to
make a specified amount using valid Indian Rupee coins. The greedy algorithm
repeatedly selects the largest denomination that fits into the remaining amount.

Valid Indian Coin Denominations:

₹1, ₹2, ₹5, ₹10

Example:

To make ₹18 using the greedy algorithm:

1. Start with ₹10: Take one ₹10 coin (₹18 - ₹10 = ₹8 left).
2. Next, ₹5: Take one ₹5 coin (₹8 - ₹5 = ₹3 left).
3. Next, ₹2: Take one ₹2 coin (₹3 - ₹2 = ₹1 left).
4. Finally, ₹1: Take one ₹1 coin (₹1 - ₹1 = ₹0 left).

Total coins used: 4 (1×₹10, 1×₹5, 1×₹2, 1×₹1).

Motivations for the Greedy Approach

The Greedy Approach is an effective problem-solving strategy due to several key

motivations:

1. Simplicity and Ease of Implementation

o Straightforward Logic: Makes optimal local choices, simplifying
understanding and implementation.
o Minimal Requirements: Requires less complex data structures

2. Efficiency in Time and Space

o Fast Execution: Suitable for large inputs.
o Low Memory Usage: Uses minimal memory by avoiding extensive
intermediate storage.
3. Optimal Solutions for Specific Problems
o Greedy-Choice Property: Local optimal choices lead to a global optimum.
o Optimal Substructure: Global optimal solutions can be built from optimal
subproblem solutions.
4. Real-World Applicability
o Practical Applications: Used in scheduling, network routing, and resource
allocation.
o Quick, Near-Optimal Solutions: Offers efficient solutions when exact results
aren't necessary.

Characteristics of Greedy Algorithms

1. Local Optimization
o Makes the best possible choice at each step using only current state
information.
2. Irrevocable Decisions
o Choices are final; no backtracking or revision of earlier decisions.
3. Problem-Specific Heuristics
o Relies on heuristics tailored to the problem's properties for decision-making.
4. Optimality
 o
Guarantees optimal solutions for problems like coin change, Huffman coding,
and Kruskal's algorithm, but not universally applicable.
5. Efficiency
o High efficiency in time and space due to reliance on local information and
limited exploration of solutions.

Pr o b l e m ( T as k C o m p l eti o n Pr o bl e m )
Given an array of positive integers each indicating the completion time for a task, find the maximum
number of tasks that can be completed in the limited amount of time that you have.

Consider the example usage with c o m p l e t i o n _ t i m e s = [ 2, 3, 1, 4, 6]

and a v a i l a b l e _ t i m e = 8

Steps:

1. Sort Tasks: Arrange tasks by completion time (ascending).

2. Iterate & Track: Add tasks sequentially as long as the total time doesn’t exceed the
limit. Update the task count accordingly.

• After sorting: [1, 2, 3, 4, 6]

• Iterating:

– Add task with time 1: total_time = 1, task_count = 1

– Add task with time 2: total_time = 3, task_count = 2

– Add task with time 3: total_time = 6, task_count = 3

– Next task with time 4 would exceed available_time, so the loop

breaks.

The maximum number of tasks that can be completed in 8 units of time is 3.

Program:

def max_tasks(completion_times, available_time):

completion_times.sort() # Step 1: Sort tasks by completion times

total_time = 0

task_count = 0

# Step 2: Iterate through the sorted list of tasks

for time in completion_times:

if total_time + time <= available_time:

total_time += time

task_count += 1

else:

break

return task_count

# Example usage

completion_times = [2, 3, 1, 4, 6]

available_time = 8

print(f"Maximum number of tasks that can be completed:

{max_tasks(completion_times, available_time)}")
Comparison between Dynamic programming and Greedy Approach

Advantages and Disadvantages

 Advantages

 Easy to implement: Greedy algorithms are relatively easy to understand and

implement.

 Time complexity: Greedy algorithms usually have a smaller time complexity.

 Optimization: Greedy algorithms can be used for optimization or to find solutions

that are close to optimal for hard problems.

 Disadvantages

 Not guaranteed to find the best solution: Greedy algorithms may not find the best
solution because they don't consider all the data.

 Local optima: Greedy algorithms may get stuck in local optima and fail to find the
global optimum.

 Lack of backtracking: Once a decision is made, it cannot be undone.

 Dependence on problem structure: Greedy algorithms may not work well for
problems that don't fit the greedy paradigm.

 Lack of rigorous proof: Greedy algorithms often lack a rigorous proof of correctness