Source1: Geeks for Geeks Youtube Video
Someone has $5 $10 $20, the other person wants $35, but he has to give a minimum number of coins.
idea: at each iteration, add coins of the largest value that does not take us past the amount to be paid. So we try 20 first, then 10, then 5.
Greedy Algorithm: an algorithmic paradigm that follows the problem solving approach of making the locally optimal choice at each stage with the hope of finding a global optimum.
- Pro: simple, easy to implement, run fast
- Cons: very often they do not provide a global optimal result.
When to use the greedy algorithm?
- Greedy-choice property: A global optimum can be arrived at by selecting a local optimum. You will never need to reconsider your earlier choices.
- Optimal Substructure: An optimal solution to the problem contains an optimal solution to subproblems. (this makes the greedy algorithm differ from dynamic programming) In other words, we can solve larger problems given the solutions to its smaller subproblems. Here is a good video for explaining the Principle of Optimality. If a problem has optimal substructure, then we should be able to use dynamic programming to solve it.
Difference between greedy algorithm and DP (dynamic programming)?
- DP considers the current problem and previously solved sub-problem together to calculate the optimal solution. The greedy algorithm only considers the current most optimal solution.
- DP requires memorization (of previously solved sub-problems), the greedy problem does not look back or revise previous choices.
- Example of DP: Bellman-Ford Algorithm; Example of Greedy Algorithm: Dijkstra’s Shortest Path.
Examples:
- Activity Selection Problem. Example: Leetcode Meeting Room II
- Scheduling Problem
- Fractional Knapsack Problem
- Job Sequencing Problem
- Dijkstra’s Algorithm for Shortest Paths from a Single Source
- Prim’s Minimum Spanning Tree
Leetcode:
Meeting Room II
