Python Data Structure and Algorithm Tutorial – Greedy Algorithm

Greedy Algorithm


In this tutorial, you will learn what a Greedy Algorithm is. Also, you will find an example of a greedy approach.

A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment, without worrying about the future result it would bring. In other words, the locally best choices aim at producing globally best results.

This algorithm may not be the best option for all the problems. It may produce wrong results in some cases.

This algorithm never goes back to reverse the decision made. This algorithm works in a top-down approach.

The main advantage of this algorithm is:

  1. The algorithm is easier to describe.
  2. This algorithm can perform better than other algorithms (but, not in all cases).


Feasible Solution

A feasible solution is the one that provides the optimal solution to the problem.

Greedy Algorithm

  1. To begin with, the solution set (containing answers) is empty.
  2. At each step, an item is added into the solution set.
  3. If the solution set is feasible, the current item is kept.
  4. Else, the item is rejected and never considered again.


Example – Greedy Approach

Problem: You have to make a change of an amount using the smallest possible number of coins.
Amount: $28

Available coins:
  $5 coin
  $2 coin
  $1 coin


  1. Create an empty solution-set = { }.
  2. coins = {5, 2, 1}
  3. sum = 0
  4. While sum ≠ 28, do the following.
  5. Select a coin C from coins such that sum + C < 28.
  6. If C + sum > 28, return no solution.
  7. Else, sum = sum + C.
  8. Add C to solution-set.


Up to the first 5 iterations, the solution set contains 5 $5 coins. After that, we get 1 $2 coin and finally, 1 $1 coin.

Greedy Algorithm Applications

  • Selection Sort
  • Knapsack Problem
  • Minimum Spanning Tree
  • Single-Source Shortest Path Problem
  • Job Scheduling Problem
  • Prim’s Minimal Spanning Tree Algorithm
  • Kruskal’s Minimal Spanning Tree Algorithm
  • Dijkstra’s Minimal Spanning Tree Algorithm
  • Huffman Coding
  • Ford-Fulkerson Algorithm



Python Example for Beginners

Two Machine Learning Fields

There are two sides to machine learning:

  • Practical Machine Learning:This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.
  • Theoretical Machine Learning: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.

Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes

Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!

Latest end-to-end Learn by Coding Recipes in Project-Based Learning:

Applied Statistics with R for Beginners and Business Professionals

Data Science and Machine Learning Projects in Python: Tabular Data Analytics

Data Science and Machine Learning Projects in R: Tabular Data Analytics

Python Machine Learning & Data Science Recipes: Learn by Coding

R Machine Learning & Data Science Recipes: Learn by Coding

Comparing Different Machine Learning Algorithms in Python for Classification (FREE)

Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.  

Google –> SETScholars