Greedy Method

Greedy Method of Problem Solving

The Greedy Method is a problem-solving strategy in which we make the best-looking choice at the current step and continue making similar choices until the problem is solved.

The important idea is:

“Choose what looks best now, without worrying too much about future choices.”

Once a choice is made, it is normally not changed or reconsidered.

---

1. How Does the Greedy Method Work?

The greedy approach generally follows these steps:

1. Identify the choices available.
2. Choose the best option at the current moment.
3. Accept the choice and do not change it later.
4. Reduce the remaining problem.
5. Repeat until the complete solution is obtained.

Simple idea

Problem
   ↓
Make the best choice NOW
   ↓
Reduce the problem
   ↓
Make the best choice NOW
   ↓
Reduce the problem
   ↓
Continue until solution is obtained

---

2. Real-Life Example – Choosing Coins

Suppose you need to pay ₹87 using coins of:

₹25, ₹10, ₹5, ₹1

You want to use the minimum number of coins.

A greedy strategy says:

Step 1

Choose the largest coin that does not exceed ₹87.

₹25

Remaining:

87 - 25 = ₹62

Step 2

Again choose the largest possible coin:

₹25

Remaining:

62 - 25 = ₹37

Step 3

Choose another ₹25:

37 - 25 = ₹12

Step 4

Choose ₹10:

12 - 10 = ₹2

Step 5

Choose two ₹1 coins:

2 - 1 - 1 = 0

Therefore:

₹25 + ₹25 + ₹25 + ₹10 + ₹1 + ₹1

Number of coins:

3 + 1 + 2 = 6 coins

So the greedy solution is 6 coins.

Why is this called greedy?

At every step, we choose the largest denomination available, because it appears to be the best choice at that moment.

---

3. Important Point: Greedy Does Not Always Work

This is a very important concept for students.

Suppose the available coins are:

₹1, ₹3, ₹4

and we need to make:

₹6

A greedy method chooses:

₹4

Remaining:

₹2

Then:

₹1 + ₹1

So greedy gives:

₹4 + ₹1 + ₹1 = ₹6

Number of coins = 3

But a better solution is:

₹3 + ₹3 = ₹6

Number of coins = 2

Therefore:

Greedy found a solution, but it did not find the optimal solution.

This demonstrates an important limitation of the greedy method.

---

4. Characteristics of the Greedy Method

1. Local optimal choice

At every step, choose what appears to be the best option right now.

2. No reconsideration

Once a decision is made, the algorithm normally does not go back and change it.

3. Fast and simple

Because it does not explore every possible solution, greedy algorithms are often efficient.

4. May or may not produce the optimal solution

Greedy works perfectly for some problems, but not for all problems.

---

5. Advantages of the Greedy Method

✅ 1. Simple to understand

The logic is usually straightforward:

Look at the available choices and select the best one.

✅ 2. Easy to implement

Greedy algorithms generally require less complicated code compared with techniques such as dynamic programming or backtracking.

✅ 3. Efficient

Since the algorithm does not usually explore all possible solutions, it can be very fast.

✅ 4. Requires less memory

Greedy algorithms usually do not need large tables to store intermediate results.

✅ 5. Useful for large problems

For suitable problems, greedy algorithms can handle large inputs efficiently.

✅ 6. Produces optimal solutions for certain problems

For problems having the greedy-choice property and optimal substructure, a greedy strategy can produce the globally optimal solution.

Examples include:

• Activity Selection
• Huffman Coding
• Kruskal's Algorithm
• Prim's Algorithm
• Dijkstra's Algorithm (with non-negative edge weights)

---

6. Disadvantages of the Greedy Method

❌ 1. Does not always give the optimal solution

This is the biggest limitation.

As we saw:

Coins = ₹1, ₹3, ₹4
Amount = ₹6

Greedy:

4 + 1 + 1 → 3 coins

Optimal:

3 + 3 → 2 coins

❌ 2. Decisions cannot normally be changed

Once a choice is made, greedy does not normally go back and reconsider it.

❌ 3. Future consequences may be ignored

The algorithm concentrates on the current choice and may fail to recognize that a different current choice would produce a better overall solution.

❌ 4. Requires proof of correctness

Before using a greedy strategy, we need to establish that the local choices will actually lead to a global optimum.

❌ 5. Not suitable for every optimization problem

Some problems require Dynamic Programming, Backtracking, or other approaches because greedy choices can lead to poor solutions.

---

8. Summary for Students

The Greedy Method is a problem-solving strategy that:

• makes the best local choice at every step,
• moves forward without normally changing previous decisions,
• is simple, fast, and memory-efficient,
• but does not always guarantee the best overall solution.

Key phrase to remember

“Choose the best now, hoping it leads to the best overall solution.”

The crucial question before applying a greedy algorithm is:

“Can I prove that making the best choice now will lead to the best final solution?”

If the answer is yes, the greedy method can be an excellent algorithmic strategy.

Example: ( University Question)

You are given an array of positive integers where each integer represents the time taken to complete the task.Develop a greedy algorithm to determine the maximum number of tasks you can complete in a given total time limit.

The greedy algorithm prioritizes tasks that take the least time first. This strategy maximizes the number of tasks completed before the total time is exhausted.

---

Steps in the Algorithm

1. Sort the Task Times in Ascending Order:

   • Reasoning: By starting with the smallest task times, you leave more total time available for other tasks.

2. Iterate Through the Sorted List:

   • Keep a running total of the time spent.
   • Count how many tasks you can complete before exceeding the total time limit $T$.

3. Stop When the Total Time Limit is Exceeded:

• As soon as adding a task exceeds the total time $T$, stop the iteration since no further tasks can be added without exceeding the limit.

Example Execution

Input:

• TaskTimes = [3, 1, 2, 5, 8]
• T = 10

Steps:

Sort the Array:

• TaskTimes = [1, 2, 3, 5, 8]

1. Iterate:

   • $\text{Total Time} = 0, \text{Task Count} = 0$
     
   • Add 1: $\text{Total Time}=1,\text{Task Count}=1$
   • Add 2: $\text{Total Time} = 3, \text{Task Count} = 2$
     
   • Add 3: $\text{Total Time} = 6, \text{Task Count} = 3$
     
   • Add 5: $\text{Total Time} = 11$ (exceeds limit, stop here)

2. Result:

   • Maximum tasks completed: 3