Table of Content

Introduction to Greedy Algorithm

• Greedy algorithms make the best immediate choice at each step, aiming for the best overall solution.
• Decisions are made based on current knowledge, without considering future consequences.
• Simple and fast, though it may not always lead to the optimal solution.

Example: Paying Exact Amount

• Objective: Pay an exact amount with the fewest coins.
• Method: Choose the highest value coin less than the remaining amount to be paid.
• Illustration: Paying 39 rupees using 20, 10, 5, and two 2-rupee coins, totaling 5 coins.

Characteristics of Greedy Algorithms

• Optimization method seeking the best local choices.
• Works well in many practical situations due to simplicity and speed.

Steps to Create a Greedy Solution

1. Define the objective (e.g., maximize total value, minimize path length).
2. Set up a process to make the best local choices at each step.

Example: Travelling Salesman Problem

• Illustration: Choosing the shortest path at each step may not lead to the best overall path.
• Shows the limitation of greedy algorithms: they may not always yield the globally optimal solution.

Fractional Knapsack Problem